排序空间复杂度与稳定性

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）的排序算法