各种排序算法的比较及应用(王道)

1.内部排序算法的比较

排序算法一般基于五个因素进行对比：时间复杂度、空间复杂度、稳定性、适用性和过程特征

1.时间复杂度：

算法	平均	最好	最坏	备注
简单选择排序	$O(n^2)$			与序列初始状态无关
直接插入排序	$O(n^2)$	$O(n)$
冒泡排序	$O(n^2)$	$O(n)$
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	在$O(n)$时间建堆，在$O(nlog_2n)$完成排序 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序
希尔排序	—无法确定—	————————	————————	插入排序变形; 对于大规模数据效率高 但无精确渐进时间
快速排序	$O(nlog_2n)$		$O(n^2)$	基于分治思想，通常是最优排序
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	基于分治思想，但其分割子序列与初始序列无关
基数排序	$O(d*(n+r))$	$O(d*(n+r))$	$O(d*(n+r))$

2. 空间复杂度：

算法	均只需要常数个辅助空间	备注
简单选择排序	$O(1)$	无
直接插入排序	$O(1)$	无
冒泡排序	$O(1)$	无
希尔排序	$O(1)$	无
堆排序	$O(1)$	无

快速排序	（平均）$O(log_2n)$	(最坏)$O(n)$	需要借助一个递归工作站

二路归并排序	$O(n)$	需要借助B[n]辅助数组帮助完成排序 虽然可以有替代方案，但是相应的时间复杂度会提升

基数排序	$O(r)$	用于r个辅助队列

计数排序	$O(n+k)$	n个输出数组+k个计数数组

3.稳定性：

稳定	不稳定
插入排序 $o(n^2)$	简单选择排序 $o(n^2)$
冒泡排序 $o(n^2)$	快速排序 $o(n*log_2n)$
归并排序 $O(log_2n)$	希尔排序 (难以计算)
基数排序 $O(d*(n+r))$	堆排序 $o(n*log_2n$
计数排序 $O(n+k)$	桶排序（？）

4.适用性：

顺序存储	顺序|链式
折半插入排序	直接插入
希尔排序	冒泡
快速排序	简单选择排序
堆排序	归并排序
	基数排序

5.过程特征：

不同排序算法在处理一趟或几趟后的结果通常是不同的且有一定特征，如

• 快速排序一趟处理至少能确定一个元素的最终位置；
• 冒泡、简单选择、堆排序每趟处理后都能产生当前的最大值或最小值；

---

2.内部排序算法的应用

1.选取排序算法需要考虑的因素：

1. 待排序元素的个数n —— 数据的规模，对于基数排序、计数排序来说，数据规模不大的话，效率 很高
2. 待排序元素的初始状态 —— 数据的初始状态也会影响，比如冒泡等算法；但不会影响 简单选择、归并排序
3. 关键字的结构及其分布情况 —— 对于堆排序影响比较大
4. 稳定性要求
5. 存储结构及辅助空间的大小限制

2. 小结:

n较小	直接插入或简单选择，直接插入移动次数相比简单排序多，数据量较大，简单选择更合适
n较大	时间复杂度为$O(log_2)$算法(快速、堆、归并) ——关键字随机分布 —- 快速排序最好 ——辅助空间需要少 —- 堆排序更好 ——稳定性好 —- 归并排序更好
若序列基本有序	直接插入 | 冒泡排序
n很大且关键字字位数小，可分解	基数排序更好
当n很大，为避免消耗移动记录时间	用链表作为存储结构

在基础比较算法的排序中，每次比较关键字的大小后，仅可能出现两种转移（向前|向后)，所以看作一颗二叉树， 所以至少需要$O(n*log_2n)$的时间,适用于任何比较类排序算法