思路
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成個(gè)組，所有距離為的記錄分在同一組內(nèi)，并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，取，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。
所以，由上述我們可知：希爾排序，是多組的直接插入排序，如果不了解直接插入排序，可參考這篇文章：直接插入排序
所以，先選定一個(gè)gap值，讓其分組，再排序。
但是，最后gap的值總歸會(huì)等于1，完成最后的排序，只不過此時(shí)的數(shù)組基本趨近于有序，此時(shí)的直接插入的時(shí)間復(fù)雜度就比較低。
但是要實(shí)現(xiàn)希爾排序，gap應(yīng)該怎么設(shè)定呢？
首先要確保，最后一組的gap必須是1，所以我們這樣規(guī)定：gap = gap / 3 + 1
這樣就可以保證最后一個(gè)的gap總是1文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-798535.html
ShellSort
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-798535.html
//希爾排序
void ShellSort(int* a, int n)
{
int gap = n;
//預(yù)排序
while (gap > 1)
{
//單趟排序
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
}
//直接插入排序
//InsertSort(a, n);
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu) | 希爾排序法】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
