数据结构浙江大学整理（4）

10.4 排序算法的比较

前三种排序算法的共同优点是算法编写简单。冒泡排序和直接插入排序每次都是交换两个元素，因此是慢的，但是它们稳定，简单选择排序是跳着交换，有可能不稳定。

希尔排序算法打破了N的平方的复杂度，它的好坏取决于d（增量序列），因为是跳着排的，所以它也是不稳定的。

堆排序和归并排序的时间复杂度是最好的，无论何时都是一样的。归并排序的缺点是它需要一个额外的空间，当数据量非常大的时候，只能排一半数据，但是它的优点是它是稳定的。堆排序理论上看很美，实际情况是虽然理论上是O(NlogN)，但是O这个常数会比较大，所以它到底跟快速排序哪个快，就难说了。堆排序和快速排序的共同缺点是不稳定，快速排序总可以构造一种最糟糕的情况是O(N2)，而且因为是递归的，所以额外空间是需要的，时间复杂度最好时，额外空间复杂度也是O(logN)。

基数排序在某种情况下，会打破NlogN的魔咒，会更快，近乎线性。它需要的额外空间是需要B个桶，每个桶设置B个数据的位置，所以到底什么情况下合算，看情况，它的好处是它是稳定的。