c++培訓(xùn)之希爾排序

希爾排序是D.L.Shell于1959年提出來的一種排序算法，在這之前的算法的時(shí)間復(fù)雜度為O(n²),希爾排序算法是突破這個(gè)時(shí)間復(fù)雜度的第一批算法之一.
希爾算法基于一種增量序列，將待排序序列分組，分別對(duì)每一組進(jìn)行插入排序。希爾排序在隨機(jī)情況下，算法的效率表現(xiàn)很優(yōu)秀。
回顧之前講過的插入排序，插入排序在序列元素較少的情況下，序列基本有序的情況下效率較高，希爾排序在插入排序基礎(chǔ)上去實(shí)現(xiàn)這兩種苛刻的要求，也就是使得每一次進(jìn)行插入排序的待排序序列元素個(gè)數(shù)較少，并使得整體元素更加有序。
使得待排序序列元素減少，那么可以使用分組，分組的策略是基于增量，可理解為相差固定個(gè)數(shù)的的元素組成組，分別對(duì)每一組進(jìn)行排序，每一組的元素個(gè)數(shù)就會(huì)減少。每一組的元素趨于有序，那么整個(gè)待排序序列也越來越趨于有序。
我們?cè)谡f到分組時(shí)，提到增量，因?yàn)樵隽筷P(guān)系到要分多少組，這個(gè)增量的算法至今沒有確切的答案，但是根據(jù)行業(yè)經(jīng)驗(yàn)，增量 = 數(shù)據(jù)個(gè)數(shù) / 3 + 1.
在進(jìn)行希爾排序中，這個(gè)增量循環(huán)調(diào)用這個(gè)增量計(jì)算公式遞減，直至增量為1時(shí)，對(duì)所有元素進(jìn)行最后一次插入排序。
希爾排序是不穩(wěn)定的排序算法，希爾排序平均時(shí)間復(fù)雜度n*log2n，最壞時(shí)間復(fù)雜度為O(n²)。下面我們來介紹希爾排序：
 

待排序序列為：9,1,5,8,3,7,4,6,2，當(dāng)增量為3時(shí)，將待排序序列分為3組：
第一組：9,8,4
第二組 : 1,3,6
第三組 : 5,7,2
分別對(duì)每一組進(jìn)行插入排序，排序后結(jié)果為：4,1,2,8,3,5,9,6,7
遞減增量為2，再分組：
第一組：4,2,3,9,7
第二組：1,8,4,6
分組對(duì)這兩組進(jìn)行排序，排序后結(jié)果為: 2,1,3,5,4,6,7,8,9
繼續(xù)遞減增量為1，對(duì)整體數(shù)據(jù)進(jìn)行一次插入排序，排序結(jié)果為:
1,2,3,4,5,6,7,8,9
實(shí)現(xiàn)代碼為:

void PrintArray(int arr[], int len){ for (int i = 0; i < len; i++){ printf("%d ", arr[i]); } printf("\n"); } //希爾排序 void ShellSort(int arr[], int len){   int increasement = len; do{   //通過算法遞減增量 increasement = increasement / 3 + 1; //獲得每一組的第一個(gè)元素下標(biāo) for (int i = 0; i < increasement; i++){ //根據(jù)第一個(gè)元素下標(biāo)+增量，遍歷每一組元素 for (int j = i + increasement; j < len; j += increasement){ //對(duì)當(dāng)前組進(jìn)行插入排序 if (arr[j] < arr[j - increasement]){   int temp = arr[j]; int k = j - increasement; for (; k >= i && temp < arr[k]; k -= increasement){ arr[k + increasement] = arr[k]; } arr[k + increasement] = temp;   }   }   }   } while (increasement > 1); } int main(){   int arr[] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 }; int len = sizeof(arr) / sizeof(int); //排序前打印 PrintArray(arr, len); ShellSort(arr, len); //排序后打印 PrintArray(arr, len);   return EXIT_SUCCESS; }

本文版權(quán)歸傳智播客C++培訓(xùn)學(xué)院所有，歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明作者出處。謝謝！
作者：傳智播客C/C++培訓(xùn)學(xué)院
首發(fā)：http://metathetuscanyresort.com/c/