希爾排序的算法代碼

希爾排序的時間復雜度為O(n*log2n) 空間復雜度為O（1）是一種不穩定的排序算法

思想：希爾排序也是一種插入排序方法,實際上是一種分組插入方法。先取定一個小於n的整數d1作為第一個增量,把表的全部記錄分成d1個組,所有距離為d1的倍數的記錄放在同一個組中,在各組內進行直接插入排序；然後,取第二個增量d2(＜d1),重復上述的分組和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有記錄放在同一組中進行直接插入排序為止。   

代碼如下：

void ShellSort(int* data ,int length)
{
    if( data == NULL || length <= 0 )
        return;

    int d = length/2;  //步長
    while( d )
    {
        for(int i = 0 ; i < d ; ++i) //根據步長分成組，對每組進行插入排序
        {
            //插入排序
            for(int j = i+d; j <length ; j +=d )
            {
                if( data[j] < data[j -d])
                {
                    int temp = data[j]; //哨兵
                    int k = j-d;
                    for(; k >=0&& temp < data[k]; k -=d)
                    {
                        data[k+d] =data[k];
                    }
                    data[k+d] =temp;
                }
            }
        }
        d = d/2;
    }
}