插入排序之希爾排序（縮小增量排序）

插入排序的特點是：

若基本有序，則時間複雜度低

若為逆序，則時間複雜度高

根據此特點，設計了希爾排序（又縮小增量排序）

讓這個序列，逐漸的變成一個有序的序列，對其進行插入排序，這樣時間複雜度就會稍低

步長為幾，就會分成幾組

最後縮小為步長為1，即對所有的元素進行一次直接插入排序。

對每組内進行直接插入排序。

#####基本思想：先将排序表分割成d個形如L[i,i+d,i+2d,…,i+kd]的“特殊”字表，分别進行​直接插入排序​，當整個表中的元素已呈現“基本有序時”，再對全體記錄進行一次直接插入排序。

比如第一次，選取的步長為3，那麼就會分為3組，對每組進行直接插入排序，之後選取步長為2，對每組進行直接插入排序，最後選取步長為1，對每組進行直接插入排序。

對于每次取步長，希爾提出來的方法是d1=(n/2)取下界，d2=(d1/2)取下界

#####希爾排序，不穩定，隻适用于順序存儲，因為對數組的編号進行操作

#####時間複雜度為O(n2),一般來說，比前兩種要效率高，因為是O(n1.3)次方

第一個for循環是逐漸縮小增量的過程，一直到增量為1

/*
*希爾排序
數組，長度
*/
void shell_sort(int *arr,int length)
{
    int temp;
    int j;
    for(int d = (length/3) + 1;d >= 1;d =d/2)
    {
        for(int i = d;i < length; ++i)
        {
            temp=arr[i];
            for(j = i-d; j >= 0 && temp < arr[j]; j = j-d)
            {
                arr[j+d]= arr[j];
            }
            arr[j+d] = temp;
        }
 
    }
 
}