比较排序

概述

比较排序（Comparison Sort） 是一类仅通过元素间的比较操作（如 $\le$、$\ge$、$<$、$>$）来获取输入元素顺序信息的排序算法。插入排序、归并排序、堆排序、快速排序 均属于比较排序。

定义

比较排序

比较排序是在运行时仅通过比较元素之间的大小关系来确定元素顺序的排序算法。在比较排序模型中，排序算法的唯一操作是读取输入元素、比较两个元素、移动元素或复制元素。

比较排序可以抽象为决策树（decision tree） 模型：每个内部节点代表一次比较，每个叶节点代表一种排列结果。

核心性质

决策树模型

• 一棵比较排序算法的决策树是一棵二叉树，每个内部节点标注为 $a_i:a_j$，表示比较 $a_i$ 和 $a_j$。
• 排序算法的执行对应于从根到叶的一条路径。
• 叶节点的数量必须至少为 $n!$（$n$ 个元素的所有排列数），因为每种排列都可能成为唯一的正确输出。

最坏情况下界

决策树的高度即为比较排序在最坏情况下所需的比较次数。一棵高度为 $h$ 的二叉树最多有 $2^h$ 个叶节点，因此：

$n!\le 2^h⟹h\ge \lg (n!)=\Omega (n\lg n)$

利用 Stirling 近似 $\lg (n!)=n\lg n-n\lg e+O(\lg n)$，可更精确地得到下界。

含义

• 任何比较排序算法在最坏情况下至少需要 $\Omega (n\lg n)$ 次比较。
• 归并排序 和 堆排序 的最坏情况 $O(n\lg n)$ 已经是渐近最优的。
• 要突破此下界，必须使用非比较排序（如 计数排序、基数排序、桶排序）。

章节扩展

第8章：排序的下界

比较排序下界的证明是第8章的理论基础，为后续非比较排序算法的必要性提供了理论依据。

参见

• 大Omega记号
• 归并排序
• 堆排序
• 计数排序