1. 章简介：排序¶

日常生活中我们经常要做排序工作： 打桥牌时整理手中的牌；整理账单和成堆的文件； 整理一罐罐香料；诸如此类。 我们有许多直观的排序策略，具体用哪种取决于要排序的对象数量 以及它们搬运起来的难易程度。 排序也是计算机最频繁执行的任务之一。 我们可能对数据库中的记录排序，以便高效地检索这批数据。 我们可能按邮政编码对客户记录排序，这样打印广告后可以用更低的 邮费寄出。 我们还可以借助排序来帮助算法解决其他问题。 例如，求 最小代价生成树 的 Kruskal 算法 在处理图的边之前，必须先按长度 对边排序。

由于排序如此重要，它自然得到了深入研究，人们设计出了许多算法。 其中一些算法是我们日常生活做法的直接改造。 例如，整理桥牌手中扑克牌的一种自然方式是：从左到右依次拿起 每张牌，把它插入到已整理好的牌中正确的位置上。 这正是 插入排序 的思想。 另一些排序算法则与人类的习惯完全不同，它们是为了排序存储在 计算机中的成千上万乃至数百万条记录而发明的。 例如，正常人不会用 快速排序 按日期整理一堆账单，尽管快速排序是大多数软件库的标准排序 算法。 经过多年研究，与排序相关的一些问题仍未解决。 针对特殊应用的新算法仍在不断开发和改进。

排序是计算机科学中的核心问题，研究排序算法还能帮助我们理解 算法设计与分析中的诸多问题。 例如，本章的排序算法展示了运用 分治 的多种途径。 特别是，"分"的方式就不止一种。 归并排序 把线性表对半分。 快速排序 把线性表按大值和 小值分。 基数排序 每次处理键的 一位数字，以此划分问题。 排序算法还能体现多种多样的算法分析技术。 快速排序表明，算法的 平均情况 增长率可能显著低于 它的 最坏情况 。 可以利用一种算法（插入排序）的 最好情况 行为来加速 另一种排序算法（如 希尔排序 或快速排序）。 某些排序算法在特殊情况下的表现使它们成为特定应用的最佳选择 （ 堆排序 ）。 排序还提供了分析问题下界的一项重要技术的示例。 外排序 指的是对存储 在磁盘上的大文件进行排序的过程。

本章介绍几种标准算法，适用于对能装入计算机内存的记录集合 排序。 首先讨论三个简单但相对较慢的算法，它们在平均情况和最坏情况下 对 \(n\) 条记录排序需要 \(\Theta(n^2)\) 时间。 接着介绍若干性能好得多的算法，其中一些的最坏情况运行时间为 \(\Theta(n \log n)\) 。 最后介绍的排序方法在特殊条件下最坏情况只需 \(\Theta(n)\) 时间（但一般情形达不到这么快）。 本章最后证明一般情形下排序在最坏情况需要 \(\Omega(n \log n)\) 时间。