希尔排序 希尔排序（），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 历史. 希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”#重定向 -{H|zh-cn:重定向;zh-tw:重新导向;}- 算法实现. 原始的算法实现在最坏的情况下需要进行O("n"2)的比较和交换。 V. Pratt的书对算法进行了少量修改，可以使得性能提升至O("n" log2 "n")。这比最好的比较算法的O("n" log "n")要差一些。 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。 假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O("n"2)的排序（冒泡排序或插入排序），可能会进行"n"次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。 一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的-{zh-hans:列; zh-hant:行;}-来进行。最后整个表就只有一-{zh-hans:列; zh-hant:行;}-了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用codice_1而不是codice_2）。 例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5-{ zh-hans:列; zh-hant:行;}-的表中来更好地描述算法，这样他们就应该看起来是这样： 然后我们对每-{zh-hans:列; zh-hant:行;}-进行排序： 将上述四-{zh-hans:行; zh-hant:列;}-数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序： 排序之后变为： 最后以1步长进行排序（此时就是简单的插入排序了）。 步长序列. 步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。 Donald Shell最初建议步长选择为formula_1并且对步长取半直到步长达到1。虽然这样取可以比formula_2类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。 已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109...)，该序列的项，从第0项开始，偶数来自formula_3和奇数来自formula_4这两个算式 （页面存档备份，存于-{zh-cn:互联网档案馆;zh-tw:网际网路档案馆;zh-hk:互联网档案馆;zh-sg:互联网档案馆;}-）。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。 另一个在大数组中表现优异的步长序列是（斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列）：(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…) 程式代码. C语言. void shell_sort(int arr[], int len) { int gap, i, j; int temp; for (gap = len » 1; gap > 0; gap »= 1) for (i = gap; i = 0 && arr[j] > temp; j -= gap) arr[j + gap] = arr[j]; arr[j + gap] = temp; C++. template void shell_sort(T array[], int length) { int h = 1; while (h = 1) { for (int i = h; i = h && array[j] = 1; step /= 2) { for (int i = step; i = 0 && arr[j] > temp) { arr[j + step] = arr[j]; j -= step; arr[j + step] = temp; C#. public void shellSort(int[]a) int h = a.Length / 2; while(h>=1) for(int i=0;i= i&&temp 0; gap »= 1) { for (let i = gap; i = 0 && arr[j] > temp; j -= gap) { arr[j + gap] = arr[j]; arr[j + gap] = temp; return arr; Python. def shell_sort(list): n = len(list) # 初始步长 gap = n // 2 while gap > 0: for i in range(gap, n): # 每个步长进行插入排序 temp = list[i] j = i # 插入排序 while j >= 0 and j-gap >= 0 and list[j - gap] > temp: list[j] = list[j - gap] j -= gap list[j] = temp # 得到新的步长 gap = gap // 2 return list PHP. function shell_sort(&$arr) {//php的阵列视为基本型别，所以必须用传参考才能修改原阵列 for ($gap = count($arr)»1; $gap > 0; $gap»=1) for ($i = $gap; $i = 0 && $arr[$j] > $temp; $j -= $gap) $arr[$j + $gap] = $arr[$j]; $arr[$j + $gap] = $temp; Go. package main import ( "fmt" func ShellSort(array []int) { n := len(array) if n 0 { for i := key; i = key && array[j] 0 for i in inc+1:length(A) j = i tmp = A[i] while j > inc && A[j - inc] > tmp A[j] = A[j-inc] j -= inc end A[j] = tmp end if inc == 2 inc = 1 else inc = floor(Int, inc * 5.0 / 11) end end return A end A = [16,586,1,31,354,43,3] println(A) # Original Array println(ShellSort(A)) # Shell Sort Array