希尔排序：基于插入算法的改进版本

平均时间复杂度：O(n log n)

最好时间复杂度：O(n log^2 n)

最坏时间复杂度：O(n log n)

稳定性：不稳定

特点：1.处理基本有序的效率较高

2.数据量比较小时效率较高

希尔排序，又名缩小增量排序，是基于插入排序的一种改进算法，解决了插入排序一次只能移动一个元素造成的低效问题。

原理

1.设定一个增量整型gap = len / 2，向下取整，根据gap分组。

2.对每一组进行插入排序。

3.更新gap = gap / 2，继续以上操作。

4.知道gap == 1停止，对所有元素执行插入排序。

代码实现

void shell_sort(int arr[], int len) {   // >>是位运算符，相当于/2并向下取整
        int gap, i, j;
        int temp; 
        for (gap = len >> 1; gap > 0; gap >>= 1)  //第一层循环，保证gap的更新
                for (i = gap; i < len; i++) {     //第二层循环，保证组别的切换
                        temp = arr[i];
                        for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)  //第三层循环，完成组内比较。
                                arr[j + gap] = arr[j];
                        arr[j + gap] = temp;
                }
}

代码解释

假设有 {4, 2, 7, 0, 5, 8}这个数组，len = 6，首先，初始的 gap = len >> 1 也就是 6 >> 1 = 3（这里的 “>>” 是右移操作符，相当于除以 2 向下取整）。此时数组根据 gap 的值被分为了两组，分别是 {4, 0} 和 {2, 5} 以及 {7, 8}。

对于第一组 {4, 0}，进入内层的插入排序循环（也就是第三层循环），因为 4 > 0，所以会将 4 往后移动（通过 arr [j + gap] = arr [j] 语句），然后把 0 放到合适的位置，即 arr [0] 的位置，这一组就排好了序。同样地，对 {2, 5} 和 {7, 8} 这两组也会进行类似的插入排序操作。

接着，更新 gap = gap >> 1，此时 gap 变为 1。这意味着现在要对整个数组当作一组来进行插入排序了。

从第二个元素开始遍历整个数组（第二层循环保证了这个遍历过程），比如对于元素 2，先把它存到临时变量 temp 中，然后通过第三层循环，与前面已经排好序的元素依次比较（这里是和 4 比较，因为 j = i - gap，此时 i 是对应元素 2 的索引，gap 为 1），如果前面的元素大于它，就把前面的元素往后移（同样是通过 arr [j + gap] = arr [j] 语句），直到找到合适的位置，再把 temp（也就是 2）放到那个位置。就这样依次对数组中的每个元素进行这样的插入排序操作，直到整个数组都排好序为止。

改进点

增量大时，分组多，组内元素比较少，效率较高。

随着增量逐渐减小，虽然组内元素越来越多，但整体越来越有序，所以效率越来越高。

不稳定性

希尔排序会改变排序前相同元素的相对位置。

例如：数组 [5*, 4, 5, 2, 8, 1]，（对不同的5加星号标记）希尔排序之后会改变两个5的相对位置，排序后的星号5出现在5的后面。

所有希尔排序具有不稳定性。