/*
ShellSort.c - by Chimomo
希尔排序又称“缩小增量排序”，是对直接插入排序方法的改进。
希尔排序的基本思想是：先将整个待排序序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
具体做法是：先取一个小于n的整数d1作为第一个增量，将所有距离为d1倍数的记录放在同一个组中，从而把全部记录分成d1组，在各组内进行直接插入排序；然后取第二个增量d2（d2<d1），重复上述分组和排序工作，依此类推，直至所取的增量di=1（di<...<d2<d1），即所有记录放在同一组进行直接插入排序为止。
希尔排序是不稳定的排序方法。
*/

void ShellSort(int data[], int n)
{
    int *delta, k, i, t, dk, j;
    /*从k = n开始，重复k = k / 2运算，直到k = 0，所得k值的序列作为增量序列存入delta*/
    k = n;
    delta = (int *)malloc(sizeof(int) * (n / 2));
    i = 0;
    do
    {
        k = k / 2;
        delta[i++] = k;
    }
    while(k > 0);
    i = 0;
    while((dk = delta[i]) > 0)
    {
        for(k = delta[i]; k < n; ++k)
        {
            /*将元素data[k]插入到有序增量子表中*/
            if(data[k] < data[k - dk])
            {
                /*备份待插入的元素，空出一个元素位置*/
                t = data[k];
                for(j = k - dk; j >= 0 && t < data[j]; j -= dk)
                {
                    /*寻找插入位置的同时元素后移*/
                    data[j + dk] = data[j];
                }
                /*找到插入位置，插入元素*/
                data[j + dk] = t;
            }
        }
        /*取下一个增量值*/
        ++i;
    }
}

/*
Main.c - by Chimomo
*/

main()
{
	int i, a[] = {48, 37, 64, 96, 75, 12, 26, 48, 54, 3};
	printf("Original array:\n");
	for(i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	ShellSort(a, 10);
	printf("Shell sorted array:\n");
	for(i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

算法 - 希尔排序（C）