各种排序算法，你值得拥有

老生常谈的东西，还是记录一下吧。

推荐阅读：https://www.cnblogs.com/chengxiao/p/6194356.html 有各种排序算法的图解、可以更方便的理解。

先上一个更老生长谈的图回忆一下，总体概览一下。（希尔排序的平均时间复杂度应该为O(nlogn)吧）

把我比较理解的几个排序方法说一下

直接插入排序：从第二个元素开始依次选择队尾的元素插入到前边一个已经有序的序列中。所以如果一开始就是有序的，则时间复杂度为O(n),空间上的话只需要一个临时变量在交换时使用。所以空间复杂度为O(1)。并且是由后向前逐个比较，没有跳跃，故直接插入是稳定的。

冒泡排序：初始有序的序列使用冒泡排序只需要比较一趟即可。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 

归并排序：是把原序列分成短序列（注意是一直划分到短序列只有一个元素或只有两个元素），各短序列自行排序后再将有序的短序列合并成一个长序列，直到原序列全部排好序。如下图所示。关于稳定性，可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。 

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤，类似于快速排序

 

直接选择排序：从第一个元素开始每次选择一个元素和后边的元素逐个比较，进行调换。所以无论有序，都需要将当前元素和后续元素逐个比较，所以时间复杂度总是为O(n^2)。在比较时可能会有跳跃性的交换，所以是不稳定的

快速排序：在序列初始有序的情况下，时间复杂度可以达到O(nlogN)。由于是通过指针进行交换，在交换时很有可能跳跃交换，所以也是不稳定的。

希尔排序：希尔排序按照步长进行分组，跨越分组容易打乱稳定性，希尔排序也是不稳定的

堆排序：假设第n个节点和第n+1个节点相等，但是在不同的层（第n个节点在第i层的最右节点，第n+1个节点在第i+1层的最左节点），通过堆排序调换后，第n+1个节点可能被调换到第i层，且在第n个节点的左侧。所以堆排序是不稳定的。