01

希爾排序算法思想

希爾排序也是一種插入排序，是簡(jiǎn)單插入排序改進(jìn)后的一個(gè)更高效版本，同時(shí)也是首批突破O（n^2）算法之一。

希爾排序算法思想：希爾排序是按照下標(biāo)增量進(jìn)行分組，對(duì)每組使用插入排序算法進(jìn)行排序，隨著增量減少，每組包含的關(guān)鍵字越來(lái)越多，增量減到1時(shí)，整個(gè)序列被分為一組，算法終止。

我們以增序排序?yàn)槔?，希爾排序基本步驟：選擇初始增量gap = length / 2，縮小增量繼續(xù)以gap = gap / 2的方式進(jìn)行，直到增量gap = 1為止，增量的每次變化都會(huì)將原始序列劃分為若干組，分別對(duì)每一組進(jìn)行插入排序。

每一次通過(guò)增量劃分組進(jìn)行插入排序宏觀上小的數(shù)移到了前面，大的數(shù)移到了后面，最后增量gap = 1進(jìn)行插入排序后就是最終的有序序列。本文會(huì)以圖解的方式詳細(xì)介紹希爾排序算法的整個(gè)工作過(guò)程。

02

希爾排序算法實(shí)現(xiàn)

希爾排序完整源碼如下：

//插入排序 void insert_sort（int *arr， int length， int start， int gap）{ if（arr == NULL || length 《= 0 || start 《 0 || gap 《= 0）{ return; } int i = 0， j = 0; int value = 0; for（i = start; i 《 length - gap; i += gap）{ value = arr［i + gap］; for（j = i; j 》= start; j -= gap）{ if（value 《 arr［j］）{ arr［j + gap］ = arr［j］; }else{ break; } } arr［j + gap］ = value; } } //希爾排序 void shell_sort（int *arr， int length）{ if（arr == NULL || length 《= 0）{ return; } int gap = 0， start = 0; int count = 0; for（gap = length / 2; gap 》 0; gap /= 2）{ start = 0; for（count = 0; count 《 length / gap; count++）{ insert_sort（arr， length， start， gap）; start++; } } }

現(xiàn)在寫(xiě)一個(gè)小程序驗(yàn)證算法的正確性，代碼如下：

#include 《stdio.h》 #include “shell_sort.h” int main（） { int i = 0; printf（“希爾排序結(jié)果 ”）; int arr［7］ = {8， 23， 64， 12， 0， 5， 6}; shell_sort（arr， 7）; for（i = 0; i 《 7; i++）{ printf（“%d ”， arr［i］）; } printf（“ ”）; return 0; }

編譯運(yùn)行輸出如下：

希爾排序結(jié)果 0 5 6 8 12 23 64

算法完全正確！

編輯：jq