c++培訓之希爾排序

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

待排序序列為：9,1,5,8,3,7,4,6,2，當增量為3時，將待排序序列分為3組：
第一組：9,8,4
第二組 : 1,3,6
第三組 : 5,7,2
分別對每一組進行插入排序，排序后結果為：4,1,2,8,3,5,9,6,7
遞減增量為2，再分組：
第一組：4,2,3,9,7
第二組：1,8,4,6
分組對這兩組進行排序，排序后結果為: 2,1,3,5,4,6,7,8,9
繼續(xù)遞減增量為1，對整體數(shù)據(jù)進行一次插入排序，排序結果為:
1,2,3,4,5,6,7,8,9
實現(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; //獲得每一組的第一個元素下標 for (int i = 0; i < increasement; i++){ //根據(jù)第一個元素下標+增量，遍歷每一組元素 for (int j = i + increasement; j < len; j += increasement){ //對當前組進行插入排序 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; }

本文版權歸傳智播客C++培訓學院所有，歡迎轉載，轉載請注明作者出處。謝謝！
作者：傳智播客C/C++培訓學院
首發(fā)：http://oisangadgets.com/c/