排序问题是计算机中最常见的问题,下面就介绍几种常见的排序方法。
以下动图均来来自菜鸟教程《十大经典排序算法》
插入排序
插入排序的步骤就像打扑克时将无需的扑克牌一张张抓拍手上的做法:
其Go语言实现代码如下:
1 | // 插入排序 |
有一种优化实现如下,即当内部循环时,不在一个一个比较,而是采用二分法找到插入位置,然后将插入位置后的数据一一后移,如下
1 | func OptInsertSort(nums []int) []int { |
选择排序
选择排序就是将序列中最小的值和第一个元素互换,然后选择剩下数组中最小的数和第二个元素互换,以此类推…
其Go语言实现代码如下:
1 | // 选择排序 |
选择排序是一种简单直观的排序算法,无论什么数据进去都是O(n²)的时间复杂度。
冒泡排序
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
其Go语言实现代码为:
1 | func BubbleSort(nums []int) []int { |
希尔排序
以上的排序方法,其平均的时间复杂度都是O(n²),以下介绍一些能突破O(n²)的排序方法。
希尔排序是插入排序的优化版本,有时也称缩小增量排序。插入排序有以下两点性质:
1. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录”基本有序”时,再对全体记录进行依次直接插入排序。
其基本的算法步骤如下:
- 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
- 按增量序列个数 k,对序列进行 k 趟排序;
- 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序。仅增量因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。
增量序列的选择十分重要,如下:
在这个例子里,前几个增量没有起到任何作用,所以一个重要要求就是增量序列之间互质,所以我们采用Hibbard增量序列,即 Dk = 22 - 1 = {1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191…},其最坏时间复杂度是O(N3/2),平均复杂度约为O(N5/4)。
其Go语言实现代码如下:
1 | // 希尔排序,Hibbard序列 |
shell排序是我在leetcode数组排序中写出的第二好运行时间的代码,高于堆排序和归并排序,仅略次于随机化快速排序。
堆排序
堆排序是指利用堆这种数据结构设计的一种排序算法,对于升序排序,我们一般采用最大堆的方式,其算法步骤如下:
- 创建一个最大堆;
- 将堆首和堆尾互换;
- 将堆的尺寸缩小1,并重新调整新的堆首以满足堆性质;
- 重复步骤2;
其Go语言代码如下:
1 | func HeapSort(nums []int) []int { |
归并排序
归并排序是建立在归并操作上的一种有效的排序算法,对于合并两个已经排序的列表,只需两个指针即可在O(N)时间内完成(N为总个数),采用以下步骤:
- 分解待排序的n个元素的序列成各具n/2个元素的两个子序列;
- 使用归并排序递归排序两个子序列;
- 合并两个已排序的子序列以产生已排序的答案。
其Go语言代码如下:
1 | // 归并排序 |
其时间复杂度始终都是O(nlgn)。
快速排序
和归并排序一样,快速排序也用到了分治的思想。其算法步骤:
- 从数组中跳出一个元素,称为“基准”(pivot);
- 重新排序数列,比基准小的摆在基准前面,比基准大的摆在基准后面;
- 递归地把小于基准元素的子数列和大于基准元素的子数列进行第1步的数列排序,直到基准左右各只有一个数;
- 因为排序是基址排序,所以无需合并。
快速排序的平均时间是O(nlgn),但是其最坏情况是O(n2),这是因为,如果原始数据的顺序性较强,总是针对于某一位置的选择基准会使得两边的数量差距太大,导致时间增长,因为有时候我们采取随机化快排的方法减少耗时。
其Go语言代码如下:
1 | // 快速排序 |
小结
以上就是针对比较排序的各种常见方法的Go语言实现。其中,比较排序拥有着Ω(nlgn)的天然下界,这是无法逾越的鸿沟,至于证明方法,可以参照书本和网络方法,这里就不赘述了。
针对比较特殊的情况,人们提出了一些线性时间排序的方法,譬如桶排序等,但是这些方法的用法条件比较严苛,比如桶排序要求数据集中在一定的范围内。