希爾排序的算法代碼

2019-11-26 16:14:28

字體：大中小

供稿：網(wǎng)友

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

思想：希爾排序也是一種插入排序方法,實(shí)際上是一種分組插入方法。先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量,把表的全部記錄分成d1個(gè)組,所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中,在各組內(nèi)進(jìn)行直接插入排序；然后,取第二個(gè)增量d2(＜d1),重復(fù)上述的分組和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?nbsp;

復(fù)制代碼代碼如下:

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) //根據(jù)步長分成組，對(duì)每組進(jìn)行插入排序
        {
            //插入排序
            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;
    }
}