插入排序
直观的插入排序isort1:
for i = [1, n) for (j=i; j > 0 && x[j-1] > x[j]; j--) swap(j-1, j)
将swap展开后得到isort2,展开代码为:
t = x[j] ; x[j] = x[j-1]; x[j-1] = t
考虑到t总是被赋予同样的值,将其挪到循环外面得到isort3:
for i = [1, n) t = x[j] for (j = i; j > 0 && x[j-1] > t; j--) x[j] = x[j-1] x[j] = t
因为内循环最后一次执行x[j] = x[j-1] 后又执行了j–,所以此时的j就是彼时的j-1。
以上三种排序算法的运行时间各自为:
程序 | 代码行数 | 纳秒(ns) |
isort1 | 3 | 11.9n2 |
isort2 | 5 | 3.8n2 |
isort3 | 5 | 3.2n2 |
简单的快速排序
快速排序算法于1962年发表,其中用到了分治法:将数组分成两个小部分,然后对它们递归排序。
简单的快速排序围绕数组的第一个元素进行划分。
void qsort1(l, u) if (l >= u) return m = l for i = [l+1, u] /* invariant: x[l+1..m] < x[l] && x[m+1..i-1] >= x[l] */ if (x[i] < x[l]) swap(++m, i) swap(l, m) qsort1(l, m-1) qsort1(m+1, u)
利用x[l]作为哨兵可以减少比较的次数,从而得到改进的qsort2。主循环改为下面的代码可以去掉主循环之后的swap操作:
m = u+1 for (i = u; i >= l; i--) if x[i] >= t swap(--m, i)
改为while循环则还可以省去内循环中的一次测试:
m = i = u+1 do while x[--i] < t ; swap(--m, i) while i != l
更好的快速排序
对于n个相同元素的数组,qsort1函数的性能很差。改进的函数qsort3可以解决这个问题,找到划分值t后,从左右两端同时向中间扫描,分别以i和j标记下标。对元素相同的情况,会停止扫描,交换i和j指向的元素的值。这样虽然使交换次数增加了,但却改进了最坏情况的时间复杂度。
void qsort3(l, u) if l >= u return t = x[l]; i = l; j = u+1 loop do i++ while i <= u && x[i] < t do j-- while x[j] > t if i > j break swap(i, j) swap(l, j) qsort3(l, j-1) qsort3(j+1, u)
进一步优化的代码qsort4主要改进了两点。一是保证随机选取划分值;二是借助于插入排序,在将数组划分为足够小的子数组后就返回,最后调用插入排序完成最后的排序。这样做排序算法的速度得到了进一步提高。
void qsort4(l, u) if u - l < cutoff return swap(l, randint(l, u)) t = x[l]; i = l; j = u+1 loop do i++ while i <= u && x[i] < t do j-- while x[j] > t if i > j break temp = x[i]; x[i] = x[j]; x[j] = temp swap(l, j) qsort4(l, j-1) qsort4(j+1, u)
调用下述代码完成一次排序:
qsort4(0, n-1) isort3()
几种快速排序的效率:
程序 | 代码行数 | 纳秒(ns) |
C库函数qsort | 3 | 137n lgn |
qsort1 | 9 | 60n lgn |
qsort2 | 9 | 56n lgn |
qsort3 | 14 | 44n lgn |
qsort4 | 15+5 | 36n lgn |
C++库函数sort | 1 | 30n lgn |
原理总结
C语言中的qsort函数和C++库函数sort排序速度都很快。如果系统中的排序能够满足我们的需求,那么就不用考虑自己编写代码了。
插入排序的代码很容易编写,且对于小型的排序任务速度很快。
借用快速排序的思想,可以在O(n)的时间内找出数组中第k个最小的元素。