冒泡排序
冒泡排序（Bubble Sort）的基本思想是：通过依次比较相邻的两个元素，判断两个元素是否满足大小关系，如果不满足则交换两个元素，每一次冒泡会让至少一个元素移动到它应该在的位置，这样n次冒泡就完成了n个数据的排序工作。冒泡排序是一种稳定排序算法。
实现过程
package main
import "fmt"
func main() {
arr := []int{8, 4, 6, 3, 0, 2}
fmt.Println(arr) // [8 4 6 3 0 2]
// 第一次冒泡
for j := 0; j < len(arr)-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
fmt.Println(arr) // [4 6 3 0 2 8]
// 第二次冒泡
for j := 0; j < len(arr)-2; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
fmt.Println(arr) // [4 3 0 2 6 8]
// 第三次冒泡
for j := 0; j < len(arr)-3; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
fmt.Println(arr) // [3 0 2 4 6 8]
// 第四次冒泡
for j := 0; j < len(arr)-4; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
fmt.Println(arr) // [0 2 3 4 6 8]
}
最终实现
package main
import "fmt"
// 冒泡排序
func BubbleSort(arr []int) {
for i := 0; i < len(arr)-1; i++ {
for j := 0; j < len(arr)-(i+1); j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
func main() {
arr := []int{8, 4, 6, 3, 0, 2}
fmt.Println(arr) // [8 4 6 3 0 2]
BubbleSort(arr)
fmt.Println(arr) // [0 2 3 4 6 8]
}
选择排序
选择排序（Selection Sort）的基本思想是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
实现过程
package main
import "fmt"
func main() {
arr := []int{8, 4, 6, 3, 0, 2}
fmt.Println(arr) // [8 4 6 3 0 2]
var key, max int
// 第一次选择
key = 0
max = arr[0]
for j := 1; j < len(arr); j++ {
// 找出最小值并记录key和val
if arr[j] < max {
key = j
max = arr[j]
}
}
// 如果第一个元素不是最小值，则把第一个元素和最大的元素替换key和val
if key != 0 {
arr[0], arr[key] = arr[key], arr[0]
}
fmt.Println(arr) // [0 4 6 3 8 2]
// 第二次选择
key = 1
max = arr[1]
for j := 1; j < len(arr); j++ {
if arr[j] < max {
key = j
max = arr[j]
}
}
if key != 1 {
arr[1], arr[key] = arr[key], arr[1]
}
fmt.Println(arr) // [0 2 6 3 8 4]
// 第三次选择
key = 2
max = arr[2]
for j := 2; j < len(arr); j++ {
if arr[j] < max {
key = j
max = arr[j]
}
}
if key != 2 {
arr[2], arr[key] = arr[key], arr[2]
}
fmt.Println(arr) // [0 2 3 6 8 4]
// 第四次选择
key = 3
max = arr[3]
for j := 3; j < len(arr); j++ {
if arr[j] < max {
key = j
max = arr[j]
}
}
if key != 3 {
arr[3], arr[key] = arr[key], arr[3]
}
fmt.Println(arr) // [0 2 3 4 8 6]
// 第五次选择
key = 4
max = arr[4]
for j := 4; j < len(arr); j++ {
if arr[j] < max {
key = j
max = arr[j]
}
}
if key != 4 {
arr[4], arr[key] = arr[key], arr[4]
}
fmt.Println(arr) // [0 2 3 4 6 8]
}
最终实现
package main
import "fmt"
// 选择排序
func SelectSort(arr []int) {
var key, max int
for i := 0; i < len(arr)-1; i++ {
key = i
max = arr[i]
for j := i + 1; j < len(arr); j++ {
if arr[j] < max {
key = j
max = arr[j]
}
}
if key != i {
arr[i], arr[key] = arr[key], arr[i]
}
}
}
func main() {
arr := []int{8, 4, 6, 3, 0, 2}
fmt.Println(arr) // [8 4 6 3 0 2]
SelectSort(arr)
fmt.Println(arr) // [0 2 3 4 6 8]
}
插入排序
插入排序（Insertion Sort）的基本思想是：把 n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
实现过程
package main
import "fmt"
func main() {
arr := []int{8, 4, 6, 3, 0, 2}
fmt.Println(arr) // [8 4 6 3 0 2]
var insertKey, insertVal int
// 第一次插入
insertKey = 1 - 1 // 第一个元素下标
insertVal = arr[1] // 第二个元素值
for insertKey >= 0 && arr[insertKey] > insertVal {
arr[insertKey+1] = arr[insertKey] // 数据后移
insertKey--
}
if insertKey+1 != 1 {
arr[insertKey+1] = insertVal
}
fmt.Println(arr) // [4 8 6 3 0 2]
// 第二次插入
insertKey = 2 - 1 // 第二个元素下标
insertVal = arr[2] // 第三个元素值
for insertKey >= 0 && arr[insertKey] > insertVal {
arr[insertKey+1] = arr[insertKey] // 数据后移
insertKey--
}
if insertKey+1 != 2 {
arr[insertKey+1] = insertVal
}
fmt.Println(arr) // [4 6 8 3 0 2]
// 第三次插入
insertKey = 3 - 1 // 第三个元素下标
insertVal = arr[3] // 第四个元素值
for insertKey >= 0 && arr[insertKey] > insertVal {
arr[insertKey+1] = arr[insertKey] // 数据后移
insertKey--
}
if insertKey+1 != 3 {
arr[insertKey+1] = insertVal
}
fmt.Println(arr) // [3 4 6 8 0 2]
// 第四次插入
insertKey = 4 - 1 // 第四个元素下标
insertVal = arr[4] // 第五个元素值
for insertKey >= 0 && arr[insertKey] > insertVal {
arr[insertKey+1] = arr[insertKey] // 数据后移
insertKey--
}
if insertKey+1 != 4 {
arr[insertKey+1] = insertVal
}
fmt.Println(arr) // [0 3 4 6 8 2]
// 第五次插入
insertKey = 5 - 1 // 第五个元素下标
insertVal = arr[5] // 第六个元素值
for insertKey >= 0 && arr[insertKey] > insertVal {
arr[insertKey+1] = arr[insertKey] // 数据后移
insertKey--
}
if insertKey+1 != 5 {
arr[insertKey+1] = insertVal
}
fmt.Println(arr) // [0 2 3 4 6 8]
}
最终实现
package main
import "fmt"
// 插入排序
func InsertSort(arr []int) {
var insertKey, insertVal int
for i := 1; i < len(arr); i++ {
insertKey = i - 1 // 前一个元素下标
insertVal = arr[i] // 元素值
for insertKey >= 0 && arr[insertKey] > insertVal {
arr[insertKey+1] = arr[insertKey] // 数据后移
insertKey--
}
if insertKey+1 != i {
arr[insertKey+1] = insertVal
}
}
}
func main() {
arr := []int{8, 4, 6, 3, 0, 2}
fmt.Println(arr) // [8 4 6 3 0 2]
InsertSort(arr)
fmt.Println(arr) // [0 2 3 4 6 8]
}
快速排序
快速排序（QuickSort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
最终实现
package main
import "fmt"
func QuickSort(arr []int, left int, right int) {
if left < right {
l, r := left, right
pivot := arr[(left+right)/2]
for l <= r {
for arr[l] < pivot {
l++
}
for arr[r] > pivot {
r--
}
if l <= r {
arr[l], arr[r] = arr[r], arr[l]
l++
r--
}
}
if left < r {
QuickSort(arr, left, r)
}
if right > l {
QuickSort(arr, l, right)
}
}
}
func main() {
arr := []int{8, 4, 6, 3, 0, 2}
fmt.Println(arr) // [8 4 6 3 0 2]
QuickSort(arr, 0, len(arr)-1)
fmt.Println(arr) // [0 2 3 4 6 8]
}