1. 介绍

排序是将一组数据，依指定的顺序进行排列的过程, 常见的排序:
1)冒泡排序
2)选择排序
3)插入排序
4)快速排序

2. 冒泡排序

2.1. 思想

通过对待排序序列从后向前(从下标较大的元素开始) ,依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元)，就象水底下的气泡一样逐渐向上冒。

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。 从而减少不必要的比较。

2.2. 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

import "fmt"

func bubbleSort(arr *[6]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() {
	var arr = [6]int{6, 5, 9, 3, 1, 3}
	bubbleSort(&arr)
	fmt.Println(arr)
}
3. 选择排序

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的。

3.1. 思想

选择排序(select sorting)也是一种简单的排序方法。

它的基本思想是:第一次从 R[0]~R[n-1]中选 取最小值，与R[0]交换，第二次从 R[1]~R[n-1]中选取最小值，与R[1]交换，第三次从 R[2]~R[n-1]中选取最小值，与R[2]交换，…，第 i 次从 R[i-1]~R[n-1]中选取最小值，与 R[i-1]交换，…, 第 n-1 次从 R[n-2]~R[n-1]中选取最小值，与 R[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

3.2. 分析

3.3. 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import "fmt"

func selectSort(arr *[6]int) {
	for i := 0; i < len(arr)-1; i++ {
		maxIndex := i + 1
		for j := i + 1; j < len(arr); j++ {
			//找到最大的下标
			if arr[maxIndex] < arr[j] {
				maxIndex = j
			}
		}
		if arr[i] < arr[maxIndex] {
			arr[i], arr[maxIndex] = arr[maxIndex], arr[i]
		}
	}
}

func main() {
	var arr = [6]int{6, 5, 9, 3, 1, 3}
	selectSort(&arr)
	fmt.Println(arr)
}
4. 插入排序

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

4.1. 思想

插入排序(Insertion Sorting)的基本思想是:把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个 元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

4.2. 分析

4.3. 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import "fmt"

func insertSort(arr *[6]int) {
	for i := 1; i < len(arr); i++ {
		index := i - 1  //指向当前元素的前一个元素下标
		value := arr[i] //当前元素的值
		for {
			if index >= 0 && arr[index] < value {
				//证明还没有找到，需要继续往下找

				//把值往后复制
				arr[index+1] = arr[index]

				//坐标往前挪动
				index--
			} else {
				//index < 0 是用来判断是不是已经找完了数组的全部。
				//如果找完了，证明就是最大
				break
			}
		}
		//有可能原地不动，此时就不要交换了
		if index+1 != i {
			arr[index+1] = value
		}
	}

}

func main() {
	var arr = [6]int{6, 5, 9, 3, 1, 3}
	insertSort(&arr)
	fmt.Println(arr)
}
5. 快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。

5.1. 思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

5.2. 分析

5.3. 实现

以中点作为判断标准(与上面分析图找的判断标准不同，上面分析图找的是最右边)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package main

import (
	"fmt"
)

//快速排序
//说明
//1. left 表示 数组左边的下标
//2. right 表示数组右边的下标
//3 array 表示要排序的数组
func QuickSort(left int, right int, array *[11]int) {
	l := left
	r := right
	// pivot 是中轴， 支点
	pivot := array[(left+right)/2]
	//for 循环的目标是将比 pivot 小的数放到 左边 // 比 pivot 大的数放到 右边
	//for 循环结束后无论pivot，在哪里。它的左边永远会比他小，它的右边永远比他大。
	for l < r {
		//从 pivot 的左边找到大于等于 pivot 的值
		for array[l] < pivot {
			l++
		}
		//从 pivot 的右边边找到小于等于 pivot 的值
		for array[r] > pivot {
			r--
		}
		// 当l==r时，证明这一轮已经全部找完了，退出循环，进行递归
		if l == r {
			l++
			r--
			break
		}
		//交换有可能是2个大小的值在两边进行交换，也有可能是我们的中间值会被交换。
		//不过结果都会是中间件的左边都是会比它小的数，右边都是比它大的数
		array[l], array[r] = array[r], array[l]

		//后面两步是因为l或者r其中有一个指向了中间值，进行了交换。
		//交换位置后，另一个值刚刚跟中间值已经比较过一次了，所以直接跳过
		if array[l] == pivot {
			r--
		}
		if array[r] == pivot {
			l++
		}
	}
	// 向左递归
	if left < r {
		QuickSort(left, r, array)
	}
	// 向右递归
	if right > l {
		QuickSort(l, right, array)
	}
}
func main() {
	arr := [11]int{-9, 78, 0, -900, 23, -567, 70, 123, 90, -23, -1200}
	fmt.Println("初始", arr)
	//调用快速排序
	QuickSort(0, len(arr)-1, &arr)
	fmt.Println("main..")
	fmt.Println(arr)
}

5.4. 提示

可以先把递归代码注释，专门理解下面代码。这段代码的执行完毕后，设置的数，比它小的肯定都在它左边，比它大的都在它右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
for l < r {
	//从 pivot 的左边找到大于等于 pivot 的值
	for array[l] < pivot {
		l++
	}
	//从 pivot 的右边边找到小于等于 pivot 的值
	for array[r] > pivot {
		r--
	}
	// 当l==r时，证明这一轮已经全部找完了，退出循环，进行递归
	if l == r {
		l++
		r--
		break
	}
	//交换有可能是2个大小的值在两边进行交换，也有可能是我们的中间值会被交换。
	//不过结果都会是中间件的左边都是会比它小的数，右边都是比它大的数
	array[l], array[r] = array[r], array[l]

	//后面两步是因为l或者r其中有一个指向了中间值，进行了交换。
	//交换位置后，另一个值刚刚跟中间值已经比较过一次了，所以直接跳过
	if array[l] == pivot {
		r--
	}
	if array[r] == pivot {
		l++
	}
}
6. 时间对比

6.1. 实现

考虑到快排的速度，所以同一用毫秒作为单位。随机从90万中取8万个数据，进行排序，比较时间差

1
2
3
4
5
6
7
8
var arr = [80000]int{}
for i := 0; i < len(arr); i++ {
	arr[i] = rand.Intn(900000)
}
start := time.Now().UnixNano()
quickSort(0, len(arr)-1, &arr)
end := time.Now().UnixNano()
fmt.Printf("快速排序:%d 毫秒\n", (end-start)/1000/1000)

6.2. 时间结果

1
2
3
4
冒泡排序:9086 毫秒
选择排序:5848 毫秒
插入排序:1254 毫秒
快速排序:7 毫秒

可以看出，快排是真的很快。以上四种都是单线程排序，快排碾压的原因是其一直在递归，每次排序都是排2个(因为2个指针调换元素)，所以会有这么惊人的速度。但是因为一直在使用递归函数，需要一直开辟新的空间，会耗费很大的cpu与内存。