第4章 排序算法
第5章 查找
第6章 图算法
第7章 人工智能中的寻路
第8章 网络流算法
第9章 计算几何
第4章 排序算法
概述
图4-1给出了一个状态列表，从这个列表中判断状态"Wyoming"是否存在，你需要多久可以完成？也许你用不了1秒就能回答这个问题。那么如果这个列表增至1000个单词，你需要花多少时间呢？乐观地估计需要100秒吧，因为这个问题的数量级增加了100倍。那么，给定同样的状态列表，你能告诉我出名字以s结尾的状态的数量吗？这个问题非常简单，你能够很快地找出答案，因为这些状态是以名字的末尾字母升序排序的。类似地，如果这个列表包含了1000个单词呢？也许只要再多花几秒就能答出来，因为你可以利用状态的有序特性。
图 4-1 10个状态的列表大量计算任务和作业因为进行了合理的排序预处理而变得简单。所以在计算机发展的早期，研究人员将大多数精力放在寻找高效的排序算法上。实际上，很多早期的算法研究都关注于大数据量的排序，早期计算机的内存不能完整地存储那些数据。相比50年前的计算机，现代计算机在计算能力和速度上都有了惊人的发展，这些需要处理的数据的数据量现在通常已经达到了太字节（Terabyte）的级别。虽然不会有人让你手工排序如此巨大的数据集，但是你还是有可能需要给数万或者数十万的数据集进行排序。在这章里，我们将介绍那些最重要的排序算法，并且根据我们的标准给出评估结果，或者告诉你哪一个算法适合解决你的问题。
术语
现在有一个可比较的数据集合A需要进行排序，我们用A[i]和ai来表示这个集合中的第i个元素。从习惯上来说，这个集合中的第一个元素被记做A[0]。为了标记方便，我们用A[low,low+n]表示含有n个元素的从A[low]到A[low+n-1]的子集合，但是A[low,low+n]却表示含有n+1个元素的从A[low]到A[low+n]的子集合。
对这个集合进行排序的要求是：如果A[i]＜A[j]，那么i＜j。如果有重复的元素，那么在结果集合中，这些重复的元素必须被相邻地排列在一起。也就是说，在一个有序的集合中，如果A[i]=A[j]，那么不存在k，使得i＜k＜j并且A[i]≠A[k]。
有序序列A是一个从原始的A序列的元素的排列。虽然有人认为根据原始的无序序列来生成新的有序序列是简单可行的，但出于对效率的考虑，下面描述的算法将会用排好的序列覆盖原始的序列。