排序系列二：希尔排序

基本思想

希尔排讯（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序方法。
希尔排序设定了一个增量d，每次插入排序使相距为d的元素排列成一个有序列，然后增量缩小，继续插入排序，最后一次d = 1，排序完成。

希尔排序.png

代码实现

void shellSort(int a[], int len){
    int i , j ,step;
    for (step = len/2 ; step > 0; step /=2) {//设置步长
        for (i = 0; i < step; i++) {//步长段直接插入排序
            for (j = i + step; j < len; j+=step) {
                if (a[j] < a[j - step]) {
                    int temp = a[j];
                    int k = j - step;
                    while (k >= 0 &&a[k] > temp) {
                        a[k + step] = a[k];
                        k -= step;
                    }
                    a[k + step] = temp;
                    
                }
            }
        }
    }
}