常见排序算法5——希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

算法描述

1）取增量gap，一般为gap=len/2；此增量未必是最优解，也可以是其它小于len的增量，关于希尔排序取最优增量分析比较复杂，大家可自行研究

2）将待排序元素按增量间隔分组

3）对每组元素进行直接插入排序

4）增量gap减半为新的gap

5）重复2-4，直至增量gap为1

算法描述

PHP代码

算法复杂度

时间复杂度：根据增量序列短的不同，其时间复杂度范围为O(n^(1.3-2))

空间复杂度：O(1)

算法稳定性

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。