7.7 各种排序方法的比较与讨论
排序在计算机程序设计中非常重要，上面介绍的各种排序方法各有优缺点，
适用的场合也各不相同。在选择排序方法时应考虑的因素有：
（ 1）待排序记录的数目 n 的大小；
（ 2）记录本身除关键码外的其它信息量的大小；
（ 3）关键码的情况；
（ 4）对排序稳定性的要求；
（ 5）语言工具的条件，辅助空间的大小等。
综合考虑以上因素，可以得出如下结论：
（ 1）若排序记录的数目 n 较小（如 n≤50）时，可采用直接插入排序或简
单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因而当
记录本身信息量较大时，用简单选择排序比较好。
（ 2）若记录的初始状态已经按关键码基本有序，可采用直接插入排序或冒
泡排序。
（ 3）若排序记录的数目n较大，则可采用时间复杂度为O（nlog2n）的排序
方法（如快速排序、堆排序或归并排序等）。快速排序的平均性能最好，在待排
序序列已经按关键码随机分布时，快速排序最适合。快速排序在最坏情况下的时
间复杂度是O（n2），而堆排序在最坏情况下的时间复杂度不会发生变化，并且所
需的辅助空间少于快速排序。但这两种排序方法都是不稳定的排序，若需要稳定
的排序方法，则可采用归并排序。
（4）基数排序可在 O(d×n)（d 为关键码的个数，当 n 远远大于 d 时）时
间内完成对 n 个记录的排序，但基数排序只适合于字符串和整数这种有明显结构
特征的关键码。当 n 很大、d 较小时，可采用基数排序。
（5）前面讨论的排序算法，除基数排序外，其它排序算法都是采用顺序存
储结构。在待排序的记录非常多时，为避免花大量的时间进行记录的移动，可以
采用链式存储结构。直接插入排序和归并排序都可以非常容易地在链表上实现，
但快速排序和堆排序却很难在链表上实现。此时，可以提取关键码建立索引表，
然后对索引表进行排序。也可以引入一个整形数组 t[n]作为辅助表，排序前令
t[i]=i，1≤i≤n。若排序算法中要求交换记录 R[i]和 R[j]，则只须交换 t[i]
和 t[j]即可。排序结束后，数组 t[n]就存放了记录之间的顺序关系。
7.8 C#中排序方法
C#语言中的许多类都提供了排序的成员方法。比如，在第四章介绍的数组
类 Array 就提供了排序方法 Sort。 Array 类中的排序方法采用的是快速排序算法，
并且要求数组中的数据元素必须实现 IComparable 接口，这样数据元素之间才能
进行比较。实际上，任何类型的数据都是使用比较器进行排序，所以，该类型要
实现排序方法，都必须实现 IComparable 接口。泛型类实现了泛型 IComparable
接口，非泛型类实现非泛型 IComparable 接口。 C#中提供了 Comparer 类来实现
各种比较器。
又比如，泛型 List 类也实现了 Sort 方法。 Sort 方法使用 Comparer 类的比较
器来决定 List<T>类中数据元素的顺序。比较器首先检查 List<T>类中数据元素是
否实现了泛型 IComparable 接口，如果实现了比较器就使用该实现，否则，比较
器再检查数据元素是否实现了非泛型 IComparable 接口，如果实现了就使用该实
现。如果这两种接口都没有实现，比较器将抛出一个 InvalidOperationException
异常 法使用了数组类 Array 的 Sort 方法。
同样，ASP.NET 2.0 中的GridView控件也实现了Sort方法。GridView控件的
类似于DataGrid控件，但比DataGrid控件更吸引人，使用更方便，程序员写
的代码也更少。Sort方法使用排序表达式和排序方向对GridVie控件进行排序。
排序表达式用于决定要排序的列，它可以对多列进行排序。排序方向决定是升序
还是降序排序。
7.7 各种排序方法的比较与讨论
排序在计算机程序设计中非常重要，上面介绍的各种排序方法各有优缺点，
适用的场合也各不相同。在选择排序方法时应考虑的因素有：
（ 1）待排序记录的数目 n 的大小；
（ 2）记录本身除关键码外的其它信息量的大小；
（ 3）关键码的情况；
（ 4）对排序稳定性的要求；
（ 5）语言工具的条件，辅助空间的大小等。
综合考虑以上因素，可以得出如下结论：
（ 1）若排序记录的数目 n 较小（如 n≤50）时，可采用直接插入排序或简
单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因而当
记录本身信息量较大时，用简单选择排序比较好。
（ 2）若记录的初始状态已经按关键码基本有序，可采用直接插入排序或冒
泡排序。
（ 3）若排序记录的数目n较大，则可采用时间复杂度为O（nlog2n）的排序
方法（如快速排序、堆排序或归并排序等）。快速排序的平均性能最好，在待排
序序列已经按关键码随机分布时，快速排序最适合。快速排序在最坏情况下的时
间复杂度是O（n2），而堆排序在最坏情况下的时间复杂度不会发生变化，并且所
需的辅助空间少于快速排序。但这两种排序方法都是不稳定的排序，若需要稳定
的排序方法，则可采用归并排序。
（4）基数排序可在 O(d×n)（d 为关键码的个数，当 n 远远大于 d 时）时
间内完成对 n 个记录的排序，但基数排序只适合于字符串和整数这种有明显结构
特征的关键码。当 n 很大、d 较小时，可采用基数排序。
（5）前面讨论的排序算法，除基数排序外，其它排序算法都是采用顺序存
储结构。在待排序的记录非常多时，为避免花大量的时间进行记录的移动，可以
采用链式存储结构。直接插入排序和归并排序都可以非常容易地在链表上实现，
但快速排序和堆排序却很难在链表上实现。此时，可以提取关键码建立索引表，
然后对索引表进行排序。也可以引入一个整形数组 t[n]作为辅助表，排序前令
t[i]=i，1≤i≤n。若排序算法中要求交换记录 R[i]和 R[j]，则只须交换 t[i]
和 t[j]即可。排序结束后，数组 t[n]就存放了记录之间的顺序关系。