插入排序：希尔排序（Shell's Sort）

希尔排序是1959年由 D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序。

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。相对直接排序有较大的改进。

操作方法：

1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2.按增量序列个数k，对序列进行k趟排序；

3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法的实现：

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

// 输出数组内容
void print(int array[], int length, int i) {
    printf("i=%d:",i);
    for (int j = 0; j < length; j++) {
        printf(" %d ", array[j]);
    }
    printf("\n");
}

// 直接插入排序的一般形式，参数 int dk 为缩小增量，如果是直接插入排序，dk=1
void ShellInsertSort(int array[], int length, int dk) {
    for (int i = dk; i < length; i++) {
        if (array[i] < array[i-dk]) { // 若第i个元素大于i-dk元素，直接插入；小于的话，移动有序表后插入
            int j = i - dk;
            int sentry = array[i]; // 复制为哨兵，即存储待排序元素
            array[i] = array[i-dk]; // 首先后移一个元素
            while (j >= 0 && sentry < array[j]) { // 查找在有序表的插入位置
                array[j+dk] = array[j];
                j -= dk; // 元素后移
            }
            array[j+dk] = sentry; // 插入到正确位置
        }
        print(array, length, i); // 打印每趟排序的结果
    }
}

// 先按增量d（n/2，n为要排序数的个数）进行希尔排序
void ShellSort(int array[], int length) {
    int dk = length / 2;
    while (dk >= 1) {
        ShellInsertSort(array, length, dk);
        dk = dk / 2;
    }
}

int main(int argc, const char * argv[]) {
    int arrayShellSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    //ShellInsertSort(arrayShellSort, 8, 1); // 直接插入排序
    ShellSort(arrayShellSort, 8); // 希尔插入排序
    printf("\n");
    
    return 0;
}

总结

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。