Question

排序（二）希尔排序、归并排序、快速排序

Answer 1

希尔排序是对插入排序的优化。希尔排序的思想：先使用数组中任间隔为h的元素有序，然后对全局进行排序。

h该怎么取值呢？如果数组长度比较小，则可设置 h=3，h=1。若数组长度比较大，可以取 h=4，但最终还是得对全局进行排序：h=1。但如果数组很长呢？则可以设置 h=10，h=4，h=1。那如果再来一个数组更加大的呢？则可以对h=22，h=10，h=4，h=1（全局排序）进行排序。所以说h的取值是一个递增序列。

我们要对一个大规模的数组进行间隔排序，再全局排序（h=1），最终得到有序的数组。

我们用其中最常用的这个。对应的时间复杂度是： 。（不推倒了，记一下）

data数组有16个元素，下面是对data中的元素进行排序：
h=4时，
开始：i从i=4，即i从数组第5个元素开始；j=i 比较j和j-4，如果是升序的，就不做任何交换了。
下一个元素：i=5，j从i开始，比较j和j-4，看是否需要交换。
...
i=8，j从i开始，将j，j-4，j-8，(间隔为4的元素)的进行排序。排序过程：先将j和j-4比较，看是否需交换；再将j-4和j-8进行比较，看是否需要交换。
....
h=1时，
开始：i从i=1，j从i开始，比较j和j-1，看是否需要交换。
i=2，j从i开始，将j，j-1，j-2，(间隔为1的元素)的进行排序。排序过程：先将j和j-1比较，看是否需交换；再将j-1和j-2进行比较，看是否需要交换。
....
i=13，j从i开始，将j，j-1，j-2，... (间隔为1的元素)的进行排序。排序过程：先将j和j-1比较，看是否需交换；再将j-1和j-2进行比较，看是否需要交换...

为了降低空间复杂度，也可以这样写：

另一种写法，开始时，将data中元素拷贝到tmp中，再对data中的元素进行操作。

归并排序总时间=子序列排好序时间+合并时间

自底向上的归并排序不是重点，把之前的那个自顶向下的归并排序弄精通了就行啦。

找到一个pivot分区点，将小于分区点的排到pivot前面，将大于分区点的排到pivot后面。

那么，如何将左边的子数组排序？还是在子数组里选择一个分区点，将小于分区点的放到前面，大于分区点的放到后面。

递推公式：sort(data, lo, hi)

当分区点选择不合理，快排的时间复杂度退化为 。比如，在升序序列中，将最后一个元素设为pivot。

当数组中有大量重复元素，上述方法会增加不必要的排序。