希尔排序

【说明】

希尔排序算法又称最小增量排序算法，其基本思想是：
步骤 1：构造一个步长序列 delta1、delta2、..、deltak，其中 delta1=n/2，后面的每个 delta 是前一个的 1/2，deltak=1：
步骤 2：根据步长序列进行 k 趟排序：
步骤 3：对第ⅰ趟排序，根据对应的步长 deta，将等步长位置元素分组，对同一组内元素在原位置上进行直接插入排序。

【代码实现】

#include <stdio.h>
#include <stdlib.h>

void shellSort(int data[], int n) {
    int *delta, k, i, t, dk, j;
    k = n;
    delta = (int *) malloc(sizeof(int) * (n / 2));
    i = 0;
    do {
        k /= 2;
        delta[i++] = k;
    } while (k > 1);

    i = 0;
    while ((dk = delta[i]) > 0) {
        for (k = delta[i]; k < n; ++k) {
            if (data[k - dk] > data[k]) {
                t = data[k];
                for (j = k - dk; j >= 0 && t < data[j]; j -= dk) {
                    data[j + dk] = data[j];
                }
                data[j+dk] = t;
            }
        }
        ++i;
    }
}


int main() {
    int A[] = {2, 5, 6, 1, 4, 7};
    int length = sizeof(A) / sizeof(int);
    shellSort(A, length);
    printf("排序后的数组：");
    for (int i = 0; i < length; i++) {
        printf("%d", A[i]);
    }
    return 0;
}

【算法分析】

时间复杂度：小于O(n^2)

算法稳定性：不稳定