上篇文章提到蠢古，插入排序在待排序列基本有序的時候，效率會好很多别凹。這篇文章介紹的希爾排序草讶，其基本思想就是先讓序列基本有序，然后再進(jìn)行插入排序炉菲。
一堕战、算法描述
希爾排序先將待排序列進(jìn)行分組，分別進(jìn)行插入排序拍霜，間隔為 gap 的元素為一組嘱丢。待各組排序完成后，逐漸縮小 gap 的值祠饺，重復(fù)分組排序過程越驻，直到 gap 值縮小為1，即對整個序列進(jìn)行一次插入排序。
gap 一般先取 n / 2 缀旁，然后逐步 gap = gap / 2 记劈，直到 gap 等于1。
二并巍、圖示舉例
下面來看一個希爾排序的圖示目木，注意觀察兩個的關(guān)鍵字為25的元素，思考一下希爾排序的穩(wěn)定性懊渡。
三刽射、算法實現(xiàn)
C語言版本代碼奉上。
void shellSort(int list[], int count) {
for (int gap = count / 2; gap >= 1; gap /= 2) {
for (int i = 0; i < gap; ++i) {
insertSort(list, count, i, gap);
}
}
}
void insertSort(int list[], int count, int head, int gap) {
int temp, i, j;
for (i = head + gap; i < count; i += gap) {
temp = list[i];
for (j = i - gap; j >= head; j -= gap) {
if (list[j] <= temp) {
break;
}
list[j+gap] = list[j];
}
list[j+gap] = temp;
}
}
可以看到剃执，希爾排序不過是一個不斷進(jìn)行插入排序的過程誓禁。在這個過程中，去不斷地調(diào)整序列的頭位置 head 和間隔 gap 的值肾档。而這里用到的插入排序算法现横，跟之前相比做了一點(diǎn)小調(diào)整，修改了待排元素的索引阁最，加上了對應(yīng)的 gap 偏移戒祠。
四、算法分析
- 開始的時候
gap值較大速种，子序列中的元素較少姜盈，排序速度較快，而且元素一次移動的距離較大配阵。 - 隨著排序的進(jìn)行馏颂，
gap值逐漸縮小，子序列中元素個數(shù)逐漸變多棋傍，但由于前面的排序結(jié)果救拉，子序列基本有序，因此排序也很快瘫拣。 - 從圖示的例子中看出亿絮，兩個關(guān)鍵字為25的元素，在排序前后麸拄，它們的相對位置已經(jīng)發(fā)生變化派昧，所以希爾排序是一種不穩(wěn)定的排序。
- 希爾排序需要比較次數(shù)和移動次數(shù)約為
n ^ 1.3拢切，當(dāng)n趨于無窮時可減少到n(log2(n))^2蒂萎。
五、總結(jié)
- 希爾排序的時間復(fù)雜度為
O( n(log2(n))^2 )淮椰。 - 希爾排序是一種不穩(wěn)定的排序五慈。
獲取更佳的閱讀體驗纳寂，請訪問原文地址 【Lyman's Blog】希爾排序——重溫排序（二）
