# 7. 排序方法的综合比较
1. 各种排序方法的性能比较
| 排序方法 | 平均时间复杂度 | 最坏时间复杂度 | 辅助存储空间 |
|---|---|---|---|
| 简单排序法 | O(n2) | O(n2) | O(1) |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(1) |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(n) |
| 基数排序 | O(d(n+rd)) | O(d(n+rd)) | O(rd) |
2. 各种排序方法的稳定性比较
| 排序方法 | 稳定性 | 反例 |
|---|---|---|
| 直接插入排序 | 是 | |
| 冒泡排序 | 是 | |
| 简单选择排序 | 否 | （3，3*，2） |
| 希尔排序 | 否 | （2，4，1，2*） d1=2，d2=1 |
| 快速排序 | 否 | （3，2，2*） |
| 堆排序 | 否 | （5，5*，3） |
| 归并排序 | 是 | |
| 基数排序 | 是 |
3. 综合分析和比较各种排序方法，可以得出以下结论：
（1）简单排序法一般只用于 n 较小的情况（例如 n<30）。当序列中的记录 “基本有序” 时，直接插入排序是最佳的排序方法。如果记录中的数据较多，则应采用移动次数较少的简单选择排序法。
（2）快速排序、堆排序和归并排序的平均时间复杂度均为 O (nlogn)，但实验结果表明，就平均时间性能而言，快速排序是所有排序方法中最好的。遗憾的是，快速排序在最坏情况下的时间性能为 O (n2)。堆排序和归并排序的最坏时间复杂度仍为 O (nlogn)，当 n 较大时，归并排序的时间性能优于堆排序，但它所需的辅助空间最多。
（3）可以将简单排序法与性能较好的排序方法结合使用。例如，在快速排序中，当划分子区间的长度小于某值时，可以转而调用直接插入排序法；或者先将待排序序列划分成若干子序列，分别进行直接插入排序，然后再利用归并排序法，将有序子序列合并成一个完整的有序序列。
（4）基数排序的时间复杂度可以写成 O (d*n)。因此，它最适用于 n 值很大而关键字的位数 d 较小的序列。当 d 远小于 n 时，其时间复杂度接近 O (n)。
（5）从排序的稳定性上来看，在所有简单排序法中，简单选择排序是不稳定的，其他各种简单排序法都是稳定的。然而，在那些时间性能较好的排序方法中，希尔排序、快速排序、堆排序都是不稳定的，只有归并排序、基数排序是稳定的。
