(转)八大排序算法稳定性分析

/ 0评 /

转自知乎:八大排序算法稳定性分析,原来稳定性是这个意思……
这是 €€F 非常喜欢的排序稳定性分析……

稳定性定义: 排序前后两个相等的数相对位置不变,则算法稳定。
稳定性的好处: 从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。

各排序算法的稳定性:

  1. 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法;
  2. 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

一、冒泡排序

二、选择排序

三、插入排序

四、快速排序

五、归并排序

六、希尔排序(shell)

七、基数排序

八、堆排序

九、各排序算法的优劣对照表

排序算法 最优时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性
插入排序 \Theta(n) \Theta(n^2) \Theta(n^2) \Theta(1) 稳定
希尔排序 \Theta(n) \Theta(n\log n) \Theta(玄学) \Theta(1) 不稳定
选择排序 \Theta(n^2) \Theta(n^2) \Theta(n^2) \Theta(1) 不稳定
堆排序 \Theta(n\log n) \Theta(n\log n) \Theta(n\log n) \Theta(1) 不稳定
冒泡排序 \Theta(n) \Theta(n^2) \Theta(n^2) \Theta(1) 稳定
快速排序 \Theta(n\log n) \Theta(n\log n) \Theta(n^2) \Theta(\log n) 不稳定
快速排序 \Theta(n\log n) \Theta(n\log n) \Theta(n\log n) \Theta(n\log n) 稳定
基数排序 \Theta(d(n+rd)) \Theta(d(r+n)) \Theta(d(r+n)) \Theta(rd+n) 稳定

(基数排序的复杂度中,r 代表关键词基数,d 代表长度,n 代表关键词个数)
(原图:https://pic1.zhimg.com/80/v2-e3a121dea092f9ec2ef727ceab030aad_hd.jpg )

From: https://zhuanlan.zhihu.com/p/36120420


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/sorting-algorithm-stability/


发表评论

电子邮件地址不会被公开。 必填项已用*标注