复习1-排序算法

简单的排序算法有三种，都是大学时学的，在这里复习。所有代码均用golang实现。容易理解的模型性能都一般，性能好的模型一般不容易理解，排序就是一个例子，涉及很多临界变量如何设置，每个算法都要有很多测试用例。

桶排序 bucket sort

这个算法纯粹是以空间换时间，初始化一个大的有序“桶”，遍历待排序数组，在相应桶上做标记。最后再格式化输出桶上标记的数组。

桶排序

优点：这个算法易理解，快，简单，时间复杂度是O(n+m), 其中 n 是待排序数组长度，m是bucket长度

缺点：bucket非常耗空间，并且要已知待排序数组最大值，如果频繁使用会造成内存空间频繁分配。生产环境下很少使用

冒泡排序 bubble sort

顾名思义，就像气泡一样轮流从水底冒到水面上。冒泡排序很好理解，每次从头遍历到尾，相邻两个元素做比较，直到找出最小的元素，置于底部。

冒泡排序

优点：简单容易理解，并且不占用额外存储空间

缺点：耗时太长，对于N长数组，时间复杂度是O(N^2)，对于时延要求很高的场景不适合，生产环境下很少使用。

快速排序 quick sort

生产环境用的最多是快速排序。我没有画图，看一下日志输出吧

第一列是原始数据，第二列是排序后的数据

94      6

120    10

79      22

22      36

166    48

81      77

81      79

120    81

160    81

197    82

10      94

36      118

118    120

183    120

6      160

82      166

3      182

77      183

182    197

每次排序所经历的路径

[10 3 6 36 22 48 81 81 120 160 197 166 79 118 183 120 82 94 77 182] 5 5

[6 3 10 36 22] 2 2

[6 3]

[36 22]

[79 81 77 81 197 166 160 118 183 120 82 94 120 182] 3 3

[77 79 81] 1 1

[77]

[81]

[182 166 160 118 183 120 82 94 120 197] 9 9

[94 166 160 118 120 120 82 182 183] 7 7

[82 94 160 118 120 120 166] 1 1

[82]

[120 118 120 160 166] 3 3

[118 120 120] 1 1

[118]

[120]

[166]

[183]

[]

快速排序

仔细读下代码，很好理解，其实就是采用分而治之的办法。先找一个基准点arr[0]，然后从数组两边向中间遍历，交换数据，使数组左面的数小于arr[0], 数组右面的数大于arr[0]。最后在递归排序左半部分数组，递归右半部分数组。

优点：会比其它方法快很多，最坏情况就是退化成冒泡排序 O(N^2)，理想情况是O(logN), 平均是O(N*logN)

缺点：不知道。。。