//使用希尔排列进行升序排列
#include <stdio.h>
#include <malloc.h>
void shellSort(int *a, int len);

int main(void)
{
    int i, len, * a;
    printf("请输入要排的数的个数：");
    scanf("%d",&len);
    a = (int *)malloc(len * sizeof(int));
    printf("请输入要排的数：\n");
    for (i = 0; i < len; i++)
	 { 
        scanf("%d",&a[i]);
    }   
    shellSort(a, len); 
    printf("希尔升序排列后结果为：\n");
    for (i = 0; i < len; i++)
	 { 
        printf("%d\t",a[i]);
    }
    printf("\n");

    return 0;
}

void shellSort(int *a, int len)
{
    int i, j, k, tmp, gap; 
    for (gap = len / 2; gap > 0; gap /= 2)
	{ 
    	for (i = 0; i < gap; ++i) 
		{ 
	        for (j = i + gap; j < len; j += gap) 
			{ 
	            tmp = a[j]; 
	            k = j - gap;
	            while (k >= 0 && a[k] > tmp)
				{
	                a[k + gap] = a[k];
	                k -= gap;
	            }
	            a[k + gap] = tmp; 
	        }
	    }
    }
}

/*①时间复杂度
希尔排序的时间复杂度依赖于增量序列的函数，有人在大量的实验后得出的结论：当n在某个特定的范围后，在最优的情况下，希尔排序的时间复杂度为O(n1.3)，在最差的情况下，希尔排序的时间复杂度为：O(n2).
空间复杂度
希尔排序的空间复杂度：O(1).
②是不稳定的排序算法
Process exited after 7.586 seconds with return value 0*/