簡介

希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因D.L.Shell于1959年提出而得名。 摘自：百度百科

代碼

算法分析

private static final void sort(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int sentinel = array[i];for (int j = i - gap; j >= 0; j -= gap) {if (array[j] > sentinel) {array[j + gap] = array[j];array[j] = sentinel;} else {break;}}}
}// 執行排序
// [27, 12, 36, 12, 24, 68, 59, 91, 45]
sort(array, 5);
// [12, 12, 36, 27, 24, 45, 59, 91, 68]
sort(array, 3);
// [12, 12, 24, 27, 36, 45, 59, 68, 91]
sort(array, 1);

實際上代碼里的sort函數本質是一個插入排序，只是序列的遍歷增量由1改為變量（gap）指定，當增量不為1時，插入排序改變的是間隔為指定增量的子列表的序列（分組排序），所以排序執行完成后，序列整體并不完全有序，直到增量為1時，排序完成后序列才會變得整體有序（實際直接執行增量為1的排序后，序列可以直接被排好序，但這個排序就就成簡單插入排序了），雖然增量不為1的排序并不能使序列整體有序，但可以將其轉換的基本有序，最后一步執行插入排序時（增量為1），將會減少元素移動的次數。 希爾排序中的步長取值沒有定論，也無法證明一個最優值，這里簡單采用列表長度減半的方式來實現

Java版

private static final void sort(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int sentinel = array[i];for (int j = i - gap; j >= 0; j -= gap) {if (array[j] > sentinel) {array[j + gap] = array[j];array[j] = sentinel;} else {break;}}}
}private static final void sort(int[] array) {// 采用列表長度減半的方式選擇排序增量，當增量為1時，排序結束for (int gap = array.length / 2; gap > 0; gap /= 2) {sort(array, gap);}
}

Python版

def shell_sort_once(lst, gap):for i in range(gap, len(lst)):key = lst[i]j = i - gapwhile j >= 0:if lst[j] > key:lst[j + gap], lst[j] = lst[j], keyelse:breakj -= gapgap = len(lst) // 2
while gap > 0:shell_sort_once(lst, gap)gap //= 2

結語

希爾排序是一種不穩定的排序（和增量的選擇有關），其本質仍是插入排序，通常來說要比插入排序效率要高（與序列本身有關，比如序列本就是有序序列，希爾排序反而不如插入排序）

PS：我在閱讀其它的希爾排序代碼，總被他們N層循環繞暈，后面當我看懂內部循環實際只是插入排序，外面是一個增量迭代的循環后，才搞清楚，我個人寫的時候通常會用函數把單次插入排序提取出來，代碼讀起來、理解起來會輕松很多。