Java 排序算法 — 总结

出处:https://github.com/iTimeTraveler/SortAlgorithms


各种排序性能对比如下,有些排序未详细介绍,暂且放到这里。实例测试结果可以看这里:八大排序算法耗时对比

排序类型 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n²) O(n) O(n²) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
直接插入排序 O(n²) O(n) O(n²) O(1) 稳定
折半插入排序 O(n²) O(n) O(n²) O(1) 稳定
希尔排序 O(n^1.3) O(nlogn) O(n²) O(1) 不稳定
归并排序 O(nlog₂n) O(nlog₂n) O(nlog₂n) O(n) 稳定
快速排序 O(nlog₂n) O(nlog₂n) O(n²) O(nlog₂n) 不稳定
堆排序 O(nlog₂n) O(nlog₂n) O(nlog₂n) O(1) 不稳定
计数排序 O(n+k) O(n+k) O(n+k) O(k) 稳定
桶排序 O(n+k) O(n+k) O(n²) O(n+k) (不)稳定
基数排序 O(d(n+k)) O(d(n+k)) O(d(n+kd)) O(n+kd) 稳定

从时间复杂度来说:

(1). 平方阶O(n²)排序:各类简单排序:直接插入、直接选择和冒泡排序

(2). 线性对数阶O(nlog₂n)排序:快速排序、堆排序和归并排序

(3). O(n1+§))排序,§是介于0和1之间的常数:希尔排序

(4). 线性阶O(n)排序:基数排序,此外还有桶、箱排序

到此,很多人会注意到基数排序的时间复杂度是最小的,那么为什么却没有快排、堆排序流行呢?我们看看下图算法导论的相关说明:

基数排序只适用于有基数的情况,而基于比较的排序适用范围就广得多。另一方面是内存上的考虑。作为一种通用的排序方法,最好不要带来意料之外的内存开销,所以各语言的默认实现都没有用基数排序,但是不能否认基数排序在各领域的应用。

时间复杂度极限

当被排序的数有一些性质的时候(比如是整数,比如有一定的范围),排序算法的复杂度是可以小于O(nlgn)的。比如:

  1. 计数排序 复杂度O( k+n) 要求:被排序的数是0~k范围内的整数
  2. 基数排序 复杂度O( d(k+n) ) 要求:d位数,每个数位有k个取值
  3. 桶排序 复杂度 O( n ) (平均) 要求:被排序数在某个范围内,并且服从均匀分布

但是,当被排序的数不具有任何性质的时候,一般使用基于比较的排序算法,而 基于比较的排序算法时间复杂度的下限必须是O( nlgn)。参考很多高效排序算法的代价是 nlogn,难道这是排序算法的极限了吗?

说明

  • 当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);
  • 而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2);
  • 原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

赞(2) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » Java 排序算法 — 总结
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏