排序空间复杂度与稳定性

8种经典排序算法已经整理完成,下面说一下他们的空间复杂度

O(1)

插入排序、冒泡排序、选择排序、希尔排序、堆排序

O(n)~O(logn)

快速排序

O(N)

归并排序

这里有一些网上和书上说可以将归并排序的空间复杂度优化到O(1),这边通过手摇算法确实可以使得空间复杂度达到O(1),但是时间复杂度会上升。

O(M)

计数排序、基数排序

这个M代表的是桶的数量

稳定性

所谓不稳定性,指的是相同元素经过排序后,改变了原数组中数的位置,即为不稳定的排序算法。

8种排序算法中,有选择排序、快速排序、希尔排序和堆排序他们是不稳定的排序算法

那么我们下面说一下,对于序列(5,5,5,1),为什么他们会是不稳定的排序算法

选择排序

选择排序,会将1与第一个5进行交换位置,导致相同元素排序后位置改变。

快速排序

对于快排而言,开始任意选择一个数,假如选到了第二个5,那么小于等于它的都将会被放到第二个5的左边,导致相同元素排序后位置改变。

希尔排序

假如希尔排序的步长选为2,在1和第二个5比较以后,会和它交换位置,导致相同元素排序后位置改变。

堆排序

将上面元素映射为大根堆,堆顶元素会和最后一个元素交换位置,导致相同元素排序后位置改变。

小结

  1. 在解决工程问题时,通常会使用多个排序算法相结合的套路,来解决问题。面对问题时要活学活用,比如使用计数排序解决按身高排序的问题很高效,但是放在解决按工资排序的问题上就不是那么好了。

  2. 一般,对于数量不大的情况下,通常选取时间复杂度为O(n^2)的插入排序算法

  3. 对于数量很大的情况下,通常选取快速排序,或者是其他的时间复杂度为O(nlogn)的排序算法