注：前七种排序是基于关键字比较的排序算法
基数排序是基于分配/收集的排序算法
（1）就平均性能而言，快速排序是最快的排序方法（即所需时间最省），（适于原始数据杂乱无章，记录数n 较大，且对稳定性没有要求的情况）但快速排序在最坏的情况下（记录正序或基本有序。轴值没有能够很好的分割数组时，即一个子数组没有结点，而另一个数组中有n-1个结点）的时间性能不如堆和归并排序。
（2）当记录基本有序或n 较大时，归并排序比堆排序的时间性能更好，但它所需的辅助存储空间最多。（归并排序适于记录n 较大，内存空间允许且要求排序稳定的情况）从时间和空间两个方面的性能考虑，堆排序的综合性能较好。
（3）当记录基本有序或n 较小时，直接插入排序是最佳的排序方法。
（4）shell 排序在数组规模达到1000时，明显好于任何一个时间复杂度为O （n ）的排序方法
（5）基数排序（适于n 值很大而关键字的构成位数较少的序列情况）的效率与原始数据的排列顺序无关
（6）简单选择排序的比较次数与序列的初始状态无关（因为它在每选出一个当前无序子序列中的最小（或最大）关键字记录的过程中都需要与无序子序列中的每个记录的关键字比较一次），但记录移动次数与序列的初始状态有关
（7）所需辅助空间量与数据规模（记录n ）无关的、且其空间复杂度为O(1)的排序方法是简单排序、希尔排序和堆排序
（8）快速排序、直接选择排序、堆排序和冒泡排序能保证每趟排序至少将一个元素放到其最终位置上
7.9
排序问题的下限
这里，我们讨论的问题是：一个问题的时间代价，而不是某个算法的时间代价
一个问题的上限（O （n ））可以定义为已知算法中速度最快的渐进时间代价，它的下限解决这个问题所有算法的最佳可能效率，包括尚未设计出来的算法。
一旦问题的上限与下限相同，从渐进分析的意义上说，不可能有更有效的算法了 基于比较的排序算法所能达到的最快速度到底有多快？
没有一种算法能够在平均及最差情况下比O (n log 2n ) 快（O (n log 2n ) ——在最坏情况下能达到的最好）
证明：所有基于比较的算法都可以归结为一棵二叉树，树的一个内部结点对应于一个比较。其次，二叉树叶结点数目最小值是n 的阶乘。
最后，具有n ﹗个叶节点的二叉树的最小深度是Ω(n log n ) 。 （详见书P163）
结论是甚至像基数排序这样的算法在平均情况下的下限也是Ω(n log n )
2
2
注：前七种排序是基于关键字比较的排序算法
基数排序是基于分配/收集的排序算法
（1）就平均性能而言，快速排序是最快的排序方法（即所需时间最省），（适于原始数据杂乱无章，记录数n 较大，且对稳定性没有要求的情况）但快速排序在最坏的情况下（记录正序或基本有序。轴值没有能够很好的分割数组时，即一个子数组没有结点，而另一个数组中有n-1个结点）的时间性能不如堆和归并排序。
（2）当记录基本有序或n 较大时，归并排序比堆排序的时间性能更好，但它所需的辅助存储空间最多。（归并排序适于记录n 较大，内存空间允许且要求排序稳定的情况）从时间和空间两个方面的性能考虑，堆排序的综合性能较好。
（3）当记录基本有序或n 较小时，直接插入排序是最佳的排序方法。
（4）shell 排序在数组规模达到1000时，明显好于任何一个时间复杂度为O （n ）的排序方法
（5）基数排序（适于n 值很大而关键字的构成位数较少的序列情况）的效率与原始数据的排列顺序无关
（6）简单选择排序的比较次数与序列的初始状态无关（因为它在每选出一个当前无序子序列中的最小（或最大）关键字记录的过程中都需要与无序子序列中的每个记录的关键字比较一次），但记录移动次数与序列的初始状态有关
（7）所需辅助空间量与数据规模（记录n ）无关的、且其空间复杂度为O(1)的排序方法是简单排序、希尔排序和堆排序
（8）快速排序、直接选择排序、堆排序和冒泡排序能保证每趟排序至少将一个元素放到其最终位置上
7.9
排序问题的下限
这里，我们讨论的问题是：一个问题的时间代价，而不是某个算法的时间代价
一个问题的上限（O （n ））可以定义为已知算法中速度最快的渐进时间代价，它的下限解决这个问题所有算法的最佳可能效率，包括尚未设计出来的算法。
一旦问题的上限与下限相同，从渐进分析的意义上说，不可能有更有效的算法了 基于比较的排序算法所能达到的最快速度到底有多快？
没有一种算法能够在平均及最差情况下比O (n log 2n ) 快（O (n log 2n ) ——在最坏情况下能达到的最好）
证明：所有基于比较的算法都可以归结为一棵二叉树，树的一个内部结点对应于一个比较。其次，二叉树叶结点数目最小值是n 的阶乘。
最后，具有n ﹗个叶节点的二叉树的最小深度是Ω(n log n ) 。 （详见书P163）
结论是甚至像基数排序这样的算法在平均情况下的下限也是Ω(n log n )
2
2