第7章 排序算法

在本章里，我们讨论对数组元素的排序问题。

为了简化问题，我们会假设数组中只包含整数。本章大部分内容假设排序能在内存完成，以便数组元素的个数相对较小，比如少于几百万个。不能在内存中执行、必须在硬盘上完成的排序也是非常重要的。本章结尾会讨论这类外部排序。

我们对内部排序的探讨将展示：

• 存在若干种容易的排序算法，比如插入排序。
• 存在一种叫希尔的排序，编码很简单，运行时间为，在实践中很有效。
• 存在若干种稍微复杂点的的排序算法。
• 任何通用型的排序算法都需要次比较。

本章剩余部分会描述和分析各种各样的排序算法。这些算法包含了有趣且重要的代码优化思路和算法设计思路。

排序算法也是一类能够被精确分析的算法。我们会在合适的地方做尽可能多的分析。