10.4 排序算法的比较
前三种排序算法的共同优点是算法编写简单。冒泡排序和直接插入排序每次都是交换两个元素,因此是慢的,但是它们稳定,简单选择排序是跳着交换,有可能不稳定。
希尔排序算法打破了N的平方的复杂度,它的好坏取决于d(增量序列),因为是跳着排的,所以它也是不稳定的。
堆排序和归并排序的时间复杂度是最好的,无论何时都是一样的。归并排序的缺点是它需要一个额外的空间,当数据量非常大的时候,只能排一半数据,但是它的优点是它是稳定的。堆排序理论上看很美,实际情况是虽然理论上是O(NlogN),但是O这个常数会比较大,所以它到底跟快速排序哪个快,就难说了。堆排序和快速排序的共同缺点是不稳定,快速排序总可以构造一种最糟糕的情况是O(N2),而且因为是递归的,所以额外空间是需要的,时间复杂度最好时,额外空间复杂度也是O(logN)。
基数排序在某种情况下,会打破NlogN的魔咒,会更快,近乎线性。它需要的额外空间是需要B个桶,每个桶设置B个数据的位置,所以到底什么情况下合算,看情况,它的好处是它是稳定的。
领取专属 10元无门槛券
私享最新 技术干货