#include <stdio.h>

#define N 20

int main()
{
    int a[N] = {
        45, 12, 78, 3, 56,
        29, 91, 17, 64, 8,
        33, 70, 1, 52, 86,
        24, 39, 95, 11, 60
    };

    int i, j, gap, temp;

    printf("排序前的数据：\n");

    for(i = 0; i < N; i++)
    {
        printf("%d ", a[i]);
    }

    // 希尔排序
    for(gap = N / 2; gap > 0; gap /= 2)
    {
        for(i = gap; i < N; i++)
        {
            temp = a[i];
            j = i - gap;

            while(j >= 0 && a[j] > temp)
            {
                a[j + gap] = a[j];
                j = j - gap;
            }

            a[j + gap] = temp;
        }
    }

    printf("\n\n希尔排序后的数据：\n");

    for(i = 0; i < N; i++)
    {
        printf("%d ", a[i]);
    }

    printf("\n");

    return 0;
}