8.6 各种排序算法的比较

从时间、空间、稳定性、适用性等方面全面比较内部排序算法，掌握选择排序算法的依据。

考查要求 ★★★ 重点掌握复杂度总表稳定性口诀趟数与初始状态算法选择

性能总表

算法	最好时间	平均时间	最坏时间	空间	稳定	适用存储
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✓	顺序、链式
折半插入排序	$O(n\log_2 n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✓	顺序
希尔排序	—	约 $O(n^{1.3})$	$O(n^2)$	$O(1)$	✗	顺序
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✓	顺序、链式
快速排序	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n^2)$	$O(\log_2 n)$	✗	顺序
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	✗	顺序、链式
堆排序	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(1)$	✗	顺序
二路归并排序	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n)$	✓	顺序、链式
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r)$	✓	顺序、链式

折半插入排序的”最好时间 $O(n\log_2 n)$ “指比较次数；由于移动次数在有序时为 0，也有教材把其最好时间写作 $O(n\log_2 n)$ 。

下面的实验在同一组数据上运行各种排序算法，统计关键字比较次数和元素移动次数。切换”随机 / 基本有序 / 完全有序 / 逆序”，验证总表中的结论：

实验同一组数据下各排序算法的比较与移动次数

n = 200

试试"完全有序"：直接插入和冒泡只需 n−1 次比较，快速排序却退化到 n²/2；简单选择排序的比较次数始终是 n(n−1)/2，与数据无关。（交换计 3 次移动）

与初始状态的关系

性质	与初始状态无关的算法
比较次数	简单选择排序、折半插入排序（比较部分）、基数排序（不比较）
移动次数	基数排序（每趟都分配收集全部元素）、归并排序（每趟都复制全部元素）
时间复杂度	简单选择 $O(n^2)$ 、堆 $O(n\log_2 n)$ 、归并 $O(n\log_2 n)$ 、基数 $O(d(n+r))$
排序趟数	直接插入（ $n - 1$ ）、简单选择（ $n - 1$ ）、基数（ $d$ ）、归并（ $\lceil\log_2 n\rceil$ ）

与初始状态有关：冒泡排序的趟数（可提前结束）、快速排序的递归深度和趟数。

若 $n$ 较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。
若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
若 $n$ 较大，则应采用时间复杂度为 $O(n\log_2 n)$ 的排序方法：快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为 $O(n\log_2 n)$ ，则可选用归并排序。
在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的 $n$ 个关键字随机分布时，任何借助于”比较”的排序算法，至少需要 $O(n\log_2 n)$ 的时间。
若 $n$ 很大，记录的关键字位数较少且可以分解时，采用基数排序较好。
当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

即时练习5 题

点击选项即可作答

1
若对 n 个元素进行排序，要求在最坏情况下时间复杂度为 O(n log₂n)，且是稳定的，则应选择（　）。
2
下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是（　）。
3
对一组数据 (2, 12, 16, 88, 5, 10) 进行排序，若前三趟排序结果如下：第一趟 2, 12, 16, 5, 10, 88；第二趟 2, 12, 5, 10, 16, 88；第三趟 2, 5, 10, 12, 16, 88。则采用的排序方法可能是（　）。
4
下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（　）。
Ⅰ. 插入排序 Ⅱ. 选择排序 Ⅲ. 冒泡排序 Ⅳ. 希尔排序 Ⅴ. 堆排序
5
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一"趟"。下列序列中，不可能是快速排序第二趟结果的是（　）。

学完了吗？

标记完成后，侧栏会显示进度。进度仅保存在本浏览器中。