希尔排序

希尔排序是改进的插入排序，又称递减增量排序
把元素通过gap分组，gap初始值可以随意取值，一般为length一半，进行组内排序，然后gap减半再次组内排序，直至为1

希尔排序.gif

#include <stdio.h>

void shellSort(int arr[],int len)
{
    int i,j,key,gap;
    for(gap=len/2;gap>0;gap=gap/2)
    {
        for(i=gap;i<len;i++)
        {
            key=arr[i];
            for(j=i;j>0;j=j-gap)
            {
                if(key<arr[j-gap])
                {
                    arr[j]=arr[j-gap];
                }
                else break;
            }
            arr[j]=key;
        }
    }
}

void main()
{
    int arr[]={1,2,3,4,9,8,7,6,5,0};
    int len = (int)sizeof(arr)/sizeof(*arr);
    printf("The order after sorting is:\n");
    shellSort(arr,len);
    for(int i=0;i<len;i++)
    {
        printf("%d  ",arr[i]);
    }

}