三、排序

排序这一研究领域在计算机科学中占有相当重要的地位，不仅仅是因为它有着广阔的应用场前景，其本身也具有理论研究意义。

排序的基本概念

对于文件而言，排序就是根据记录关键字值的递增或者递减关系将记录的次序进行重新排序，使得原来一组次序任意的记录转变为按其关键字值有序排列的一组记录。排序过程理解为一个按值无序的数据元素序列转换为一个按值有序排序的数据元素序列的过程。从小到大称为升序或者正序关系；从大到小称为逆序或者降序关系。排序又称为分类。排序能够作为提高查找时间效率的手段。

排序的分类

可以从不同观点角度将排序操作分为不同的种类。

1.内排序 和 外排序

根据排序过程中所使用的 内、外存储器情况的不同，可以将排序分为 内部排序 和 外部排序两大类。简称 内排序和外排序。
内排序是指，当参加排序的数量不大是，在排序过程中将全部信息存放在内存中处理的排序方法。当参加排序的数据量较大，以至于内存不足以依次存放全部信息，在排序过程中需要通过内存与外存之间的数据交换来达到排序目的，这种排序方式成为外排序。
外排序的速度要比内排序的速度慢很多。

2.稳定性排序 和 非稳定性排序

通常把参加排序的项称为排序码或者排序项。对于具有同一排序码的多个记录而言，若采用的排序方法使得排序后记录的相对位置保持不变，则称此排序为稳定的，否则为不稳定的，相应的排序方法为稳定性排序方法 和 非稳定排序方法，这种特性是有用的。

3.连续顺序文件排序 和 链表排序

根据 文件在存储介质上的组织方式划分排序的种类，可以分为连续顺序文件排序 和 链表排序。
连续顺序文件排序：由于记录之间的逻辑顺序是通过物理地址的先后来映射，因而在排序过程中需要移动记录的位置。
链表排序：文件中的一个记录对应着链表中的一个链结点，记录之间的逻辑顺序是通过指针来反映的，因而排序过程中不必移动记录，只需修改相应指针的指向。

内排序

内排序方法的种类很多，如果按照完成排序所需的工作量来划分，还可以将排序方法分为简单排序法、先进排序法、基数排序法3类。如果按照排序过程中采用的策略不同，还可以将排序归纳为插入排序、选择排序、交换排序、归并排序、基数排序几类。
内排序的方法虽然很多，但就其全面性而言，很难说哪一种或者哪一类方法最好，每一种方法都有它自己的优势和不足，使用者应该根据不同的环境和情况（如参加排序的序列数量的大小或者序列的初始状态等）选择较为合适的方法。

无论何种排序方法，衡量其性能的主要指标不外乎两个：其一、执行排序算法所需要的时间；另一个，执行排序算法所需要的附加空间。
对于前者，排序过程中要进行的基本动作包括：1、比较两个元素的大小，2、将元素从一个位置移动到另一个位置（采用链表排序时可以不必移动元素）。因此，排序的工作量取决于这两种动作的执行次数，尤其是前一个动作。

下面具体来介绍几种内排序方法

1. 插入排序
2. 选择排序
3. 泡排序
4. 谢尔排序
5. 快速排序
6. 堆积排序 （待完成）
7. 二路归并排序
8. 基数排序

各种内排序方法的比较

各种排序算法之间的比较主要从下面几个方面综合考虑。

1. 算法的时间复杂度
2. 算法的空间复杂度
3. 排序稳定性
4. 算法结构的复杂度
5. 参加排序的数据规模

稳定性比较

插入排序、泡排序、二路归并排序、基数排序 方法是稳定排序方法。
选择排序、谢尔排序、快速排序、堆积排序 方法是不稳定排序方法。

复杂性比较

各种内排序算法的时间复杂度和空间复杂度如下表所列：

排序方法 平均时间 最坏情况 辅助空间
插入排序 O(n2) O(n2) O(1)
谢尔排序 O(nlog2n) O(nlog2n) O(1)
冒泡排序 O(n2) O(n2) O(1)
快速排序 O(nlog2n) O(n2) O(log2n)
选择排序 O(n2) O(n2) O(1)
堆积排序 O(nlog2n) O(nlog2n) O(1)
归并排序 O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+r)) O(d(n+r)) O(n+r)

综上所述，得出如下结论：

1. 在平均情况下，谢尔排序、快速排序、堆积排序、归并排序 都能达到较快的排序速度。进一步可知，快速排序最快。从空间消费来看，堆积排序最省。
2. 在平均情况下，插入排序、冒泡排序方法的排序速度较慢，但当参加排序的序列开始就局部有序时，这两种排序方法能达到较快的排序速度。最好情况下，时间复杂度为O(n)，比情况1中叙述的4种方法要好一些，而且这两种方法辅助空间消费较少。所以当n较小、或者序列开始就局部有序时，可选择这两种方法。多数情况下可以根据不同情况与1中的4种方法结合使用。
3. 基数排序方法消费的空间较多，但其时间复杂度可简化成O(dn)；当元素的位数较少时，可进一步简化成O(n)， 在这种情况下也能达到较快的排序速度。另外，归并爱旭方法也需要的辅助空间较多。
4. 从算法结构的简单性来看，插入排序法、选择排序法、冒泡排序法 比较简单和直接；而谢尔排序法、快速排序法、堆积排序法、归并排序法 都可以看做是对某一种排序法的进一步改进。相对而言，改进后的排序法所对应的算法可能都比较复杂。
5. 从参加排序的数据序列的规模大小来看，n越小，采用简单排序方法就越合适；n越大，采用改进的排序方法越合适。这是因为n越小，n2与log2n的差距越小，并且简单排序方法的时间复杂度的系数均小于1（泡排序法的最坏情况以外），而改进后的排序方法的时间复杂度的系数均大于1，因而也使得他们之间的差距变小。

从上面的分析可以看到，很难说哪一个排序方法绝对好。每一种排序方法都有其优缺点，适合于在不同的环境下使用。因此在实际应用中，要根据具体情况选择合乎实际情况的方法。下面给出综合考虑以上几方面后所得出的大致结论，仅供在选择内排序方法是参考：

1. 当参加排序的数据规模n较大，关键字元素分布比较随机，并且不要求排序稳定性时，宜选用快速排序法。
2. 当参加排序的数据规模n较大，内存空间又允许，并且有排序稳定性要求，宜采用归并排序法。
3. 当参加排序的数据规模n较大，元素分布可能出现升序或者逆序的情况，并且对排序稳定性不要求时，宜采用堆积排序方法或者归并排序方法。
4. 当参加排序的数据规模n较小（如小于100），元素基本有序（升序），或者分布也比较随机，并且有排序稳定要求时，宜采用插入排序方法。
5. 当参加排序的数据规模n较小，对排序稳定性又不要求时，宜采用选择排序方法。

向插入排序、选择排序、归并排序 都比较容易在链表上实现，避免将大量时间花费在元素的位置移动上。像快速排序、堆积排序就很难在链表上实现。

外排序

(待完成)