希爾排序:
希爾排序法又稱縮小增量法，
希爾排序法的基本思想是：
先選定一個整數，把待排序檔案中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序，然后，取，重復上述分組和排序的作業，當到達=1時，所有記錄在統一組內排好序，
插入排序時：陣列接近有序的時候，時間復雜度趨于O(N)，
希爾排序是對于直接插入排序的優化，通過預排序使陣列趨于有序
希爾排序的分為預排序(gap > 1)和直接插入( gap == 1)排序兩步驟，
?
分組預排序使陣列接近有序：
假設 gap = 3，按照gap分組，對每一組進行插入排序，
對gap（gap=3）組預排序完畢：
對一組gap進行單趟排序：
//參考插入排序
for (int i = 0; i < n - gap; i += gap)
{
//當gap==1時就為直接插入排序
int end = 0;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}對gap（gap=3）組排序完畢：
int gap = 3;
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
// 對其中一組進行單趟的插入排序
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}進一步優化：
void ShellSort(int* a, int n)
{
int gap = n;
//若判斷條件為gap>=1則當gap=1時會多排一次
while (gap > 1)
{
//gap /= 2;
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; ++i)
{
// 對一個gap組的一個單趟排序
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}希爾排序的特性總結：
1. 希爾排序是對直接插入排序的優化，
2. 當gap > 1時都是預排序，目的是讓陣列更接近于有序，當gap == 1時，陣列已經接近有序的了，這樣就
會很快，這樣整體而言，可以達到優化的效果，我們實作后可以進行性能測驗的對比，
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定：
4. 穩定性：不穩定
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/375883.html
標籤：其他
上一篇：【藍橋杯】~C語言陣列排序
下一篇：鏈表的實作