引用:對於大規模亂序數組插入排序很慢,因為它只會交換相鄰的元素,因此元素只能一點一點的從數組的一端移動到另一端。例如,如果主鍵最小的元素正好在數組的盡頭,要將它挪到正確的位置就需要N-1次移動。希爾排序為了加快速度簡單的改進了插入排序,交換不相鄰的元素以對數組的局部進行排序,並最終用插入排序將局部有 ...
引用:對於大規模亂序數組插入排序很慢,因為它只會交換相鄰的元素,因此元素只能一點一點的從數組的一端移動到另一端。例如,如果主鍵最小的元素正好在數組的盡頭,要將它挪到正確的位置就需要N-1次移動。希爾排序為了加快速度簡單的改進了插入排序,交換不相鄰的元素以對數組的局部進行排序,並最終用插入排序將局部有序的數組排序。
int[] sort = new int[13] { 1, 4, 89, 34, 56, 40, 59, 60, 39, 1, 40, 90, 48 }; // 輸入一個數組 int h = 1; int length = sort.Length; while (h > length / 3) { h = 3 * h + 1; // 1,4,13,40,121,364,1093,... } // h的初始值根據數組元素多少而定 while (h >= 1) // 當h=1 時排序完成 { for (int i = h; i < length; i++) // 將間隔為h的元素排序 { for (int j = i; j >= h && sort[j] < sort[j - h]; j -= h) // 當滿足這兩個條件時交換 數值 { int temp = sort[j]; sort[j] = sort[j - h]; sort[j - h] = temp; } } h = h / 3; } for (int i = 0; i < sort.Length; i++) // 輸出 { Console.Write(sort[i] + " "); }
備註:文字和代碼有參考到書籍:演算法 第四版(人民郵電出版社) 希爾排序 (162-163)