// 试题四（共15分）
// 阅读下列说明和C代码，回答问题1至问题3，将解答填入答题纸的对应栏内。
// 【说明】
// 希尔排序算法又称最小增量排序算法，其基本思想是：
// 步骤1：构造一个步长序列delta1, delta2, ...., deltak, 其中delta1 = n / 2，后面的每个delta是前一个的1 / 2，deltak = 1；
// 步骤2：根据步长序列进行k趟排序；
// 步骤3：对第i趟排序，根据对应的步长delta，将等步长位置元素分，对同一组内元素在原位置上进行直接插入排序。

// 【C代码】
// 下面的算法用C语言实现
// （1）常量和变量说明
// Data：待排序数组data，长度为n，待排序数据在data[0], data[1], data[2]..., data[n - 1]中。
// N：数组data中的元素个数
// delta：步长数组

// （2）C程序
#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 = k / 2; // 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 n = 7;
    int data[] = {15, 9, 7, 8, 20, -1, 4};
    
    ShellSort(data, n);
    
    int i;
    for (i = 0; i < n; i ++ ) printf("%d ", data[i]);
    
    return 0;
}