11.2.1. 排序术语与记号¶

Settings

Saving...
Server Error
Resubmit

按照定义， 排序问题 允许输入中出现两条或更多键值相同的记录。某些应用要求输入不得包含重复的键值。除非特别说明，排序算法一般都能处理重复键。当允许重复键时，重复记录之间可能存在某种隐含的顺序，通常依据它们在输入中出现的先后次序。保持重复记录之间的这一初始顺序可能是值得的。如果排序算法不改变键值相同的记录之间的相对次序，就称它是 稳定 的。本章介绍的排序算法中有许多是稳定的，或者稍加修改即可变为稳定，但并非全部。

比较两个排序算法时，最简单的办法是把两个都实现出来，然后 测量它们的运行时间。 这是 实验比较 的一个例子。 然而，做公平的实验比较并不容易，因为许多排序算法的运行时间 依赖于输入值的具体情况。 记录的数目、键和记录的大小、键的允许取值范围，以及 输入记录"乱序"的程度，都会显著影响排序算法之间相对的运行 时间。

分析排序算法时，传统做法是统计键之间的比较次数来衡量成本。这个指标通常与算法的实际运行时间密切相关，而且具有与机器和数据类型无关的优点。但在某些情况下，记录可能非常庞大，以至于移动记录本身就要占总运行时间的相当大比例。此时，更合适的做法可能是统计算法执行的交换操作次数。在大多数应用中，我们可以假定所有记录和键都是定长的，一次比较或一次交换操作所需时间是常数，与涉及哪些键无关。然而，某些特殊情形会"改变规则"，使排序算法之间的比较方式不同。例如，记录或键长度差异悬殊的应用（如对变长字符串序列排序），不能指望每次比较的成本大致相同。这类情形不仅需要特殊的度量来分析，通常也适合采用专用的排序技术。

另一些应用只需对少量记录排序，但排序操作非常频繁。例如某个应用反复对五个数构成的组排序。在这类情形下，通常在渐近分析中被忽略的运行时间表达式中的常数因子如今变得至关重要。注意，递归排序算法最终也会对大量短小的线性表排序。

最后，有些情形要求排序算法尽可能少地使用内存。我们会特别指出那些需要输入数组之外大量额外内存的排序算法。