最新消息:2017年,我的目标是补齐数据结构、算法、操作系统和网络编程的知识,你呢?

几种排序算法的比较

技术 谷溪 427浏览 0评论

整个十一假期就在折腾这几个算法,这篇总结性文章就是简要的介绍了几个基础算法的特性,并附带了 Python 的实现。

不同算法适合不同情况的数组,但在不知道输入规律的时候,使用时间复杂度低算法的比较保险。

Big O:上界
Big Ω:下界
Big Θ:确界

Big O 比较

big_o_complexity

O(n²):冒泡排序(稳定)/选择排序(不稳定)/插入排序(稳定)
O(nlgn)~O(n²):希尔排序(不稳定)
O(nlgn):堆排序(不稳定)/归并排序(稳定)/快速排序(不稳定)

Bubble Sort 冒泡排序

时间复杂度、稳定性

平均情况:O(n²)
最坏情况:O(n²)
最好情况:O(n)
稳定
辅助空间O(1)

特点

最优情况为全部正序时经过 n-1 次比较即可完成排序,最差情况是倒序。因此冒泡算法对数组的有序性很敏感,适合对规模较小、且比较有序的数据进行排序。[1]

优化方案

  1. 如果某一次遍历没有发生数据交换,则代表已完成排序,可停止迭代。
  2. 记录遍历时最后一次数据交换的位置,后面的数据已经有序,因此可以缩小下次循环的范围。

Selection Sort 选择排序

时间复杂度、稳定性

平均情况:O(n²)
最坏情况:O(n²)
最好情况:O(n²)
不稳定
辅助空间O(1)

特点

运行时间与输入状态无关(随机排列与正序排列消耗相同的时间)。同时移动次数最少(与数组大小呈线性关系)。[1]

Insertion Sort 插入排序

时间复杂度、稳定性

平均情况:O(n²)
最坏情况:O(n²)
最好情况:O(n)
稳定
辅助空间:O(1)

特点

输入状态会影响运行效率,对有序数组排序要比对随机排列、逆序排列的数组快,因此适用于部分有序的非随机数组。当『数组中每个元素距离它的最终位置都不愿』『一个有序的大数组接一个小数组』『数组中只有几个元素的位置不正确』时,插入算法的速度很可能比其他算法都快。[2]

Shell Sort 希尔排序

时间复杂度、稳定性

平均情况:O(nlgn)~O(n²)
最坏情况:O(n²)
最好情况:O(n1.3)
不稳定
辅助空间:O(1)

特点

希尔排序将数组分成较短的子数组、并使之部分有序,很适合插入排序。希尔排序对中等大小数组的排序时间可以接受,代码量小,且不需要额外内存空间。当没有系统排序函数可用时,可以考虑先用希尔排序,再考虑是否值得替换为更复杂的排序算法。[3]

Merge Sort 归并排序

时间复杂度、稳定性

平均情况:O(nlgn)
最坏情况:O(nlgn)
最好情况:O(nlgn)
稳定
辅助空间:O(n)

特点

归并排序在最坏的情况下复杂度为O(nlgn),和其他基于比较的排序算法所需的最小比较次数相同。

Quick Sort 快速排序

用递归在 Python 中实现快速排序会遇到 RuntimeError: maximum recursion depth exceeded 的错误提示,原因是 Python 的递归深度默认为1000(可以用 sys.getrecursionlimit() 来查看),有两种方式解决为题。一种是用循环重写算法,另一种比较简单粗暴,直接用 sys.setrecursionlimit(99999) 把递归深度设置为 99999 这种大数字,更详细可参见这里

时间复杂度、稳定性

平均情况:O(nlgn)
最坏情况:O(n²)
最好情况:O(nlgn)
不稳定
辅助空间:O(nlgn)~O(n)

特点

在实际应用中,一般比其他算法快很多,内循环很小,原地排序(仅需要很小的辅助栈),且将长度为 N 的数组排序的时间与 NlgN 成正比。但很脆弱,实际性能会因某些错误变成平方级。[4]

快速排序和归并排序使用分治法和递归进行排序,但快排在合并子数组后是自然有序的大数组;归并在合并阶段则繁琐一些,还要再次进行比较。

在对数组进行切分不平衡时,会导致性能低效(例如第一次从最小元素切分、第二次从第二小的元素切分……)。解决该问题,可以对数组进行随机排序,避免性能下降到极低。

优化

  1. 快排在小数组中比插入排序慢,因此在排序小数组时使用插入排序。
  2. 三取样切分。
  3. 熵最优排序[5]

以上三种优化是《Algorithms 4th》中对于快排性能的优化,都是对算法本身做了一些改进。而最著名的优化则是《算法导论》中提到的『随机化快速排序』,与上述三种性能优化有很大不同。

随机化快速排序,一般来说都是将取主元的过程随机化。随机化快速排序的『优化』,并没有提高快排的性能,而是避免了某些序列使快排性能大幅降低到O(n²)的可能性、防止他人设计一个序列对服务器发起DoS攻击,使排序更加稳定和安全(我发现还有很多人有类似的误解)。事实上随机化快速排序和普通快速排序在时间复杂度上同为O(nlgn),实际实验中也没有显著差异。

知乎上一个用户对快排和随机快排的性能做了测试,但我猜他可能也理解错了,他所做的只是在优化随机快排的代码,但并没有显著提高算法性能或降低复杂度(知乎链接)。Thomas Cormen 在 Quora 中也回答了关于随机化快排和普通快排性能差异的问题(Quora链接),但是他本人在《算法导论》(中文版100页,英文版179页)中并没有把这个问题讲的很透彻,也许算是一个微小的失误。

Heap Sort 堆排序

时间复杂度、稳定性

平均情况:O(nlgn)
最坏情况:O(nlgn)
最好情况:O(nlgn)
不稳定
辅助空间:O(1)
2. 特点
目前唯一的能最优利用时间与空间的算法,最坏情况下也能保证 2NlgN 次比较和恒定的辅助空间。当空间紧张时(例如嵌入式),堆排序用几行代码就能实现实现较好性能。

缺点是无法利用缓存,缓存未命中的次数远高于大多数在相邻元素间比较的算法。

sort

通过倍率实验预测程序的增长数量级

可以使用倍率实验来预测任意程序的增长数量级:
每次实验时使输入翻倍,计算时间,并求两次运行时间的比值。反复运行直到比值趋近于2的b次方。[6]

算法的『稳定性』是什么

稳定性指,当排序的元素中有相同的值时,这些具有相同值的元素在排序后的前后位置是否发生变化的性质。如果变化,则不稳定;如果不变化,则稳定。在 Bubble Sort 中,相邻元素互相交换,如果两个相邻元素相等则不需交换;如果两个相等的元素彼此之间有间隔,那么即便它们和相邻元素交换后,其相对的前后位置也不会发生变化,所以是稳定的。而在 Selection Sort 中,第一个元素与最小的元素交换、第二个元素与第二小元素交换等等,间隔有可能很大从而在交换时跳过了相同值的元素,进而造成相同值元素前后位置改变,因此是不稳定的。

排序的键值有可能只是元素的一个属性,如果元素本身还具有其他属性,那么键值相同的元素排序后的相对顺序还与其他属性有关。例如用稳定的算法对员工按工资排序,假如原数组是按年龄排序的,那么月薪同为7000元的3个人在按工资排序后仍然可以保持年龄正序,即最初的相对位置不变。

参考资料:

[1]《Algorithms 4th》 P248
[2]《Algorithms 4th》 P252
[3]《Algorithms 4th》 P262
[4]《Algorithms 4th》 P288
[5]《Algorithms 4th》 P296
[6]《Algorithms 4th》 P121

转载请注明:Alien外星人 » 几种排序算法的比较

发表我的评论
取消评论

表情