希尔排序算法

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

本文地址：http://www.cnblogs.com/archimedes/p/shell-sort-algorithm.html，转载请注明源地址。

原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。V. Pratt的书对算法进行了少量修改，可以使得性能提升至O(nlog2n)。这比最好的比较算法的O(nlogn)要差一些。

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82

25 59 94 65 23

45 27 73 25 39

然后我们对每列进行排序：

10 14 73 25 23

13 27 94 33 39

25 59 94 65 82

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73

25 23 13

27 94 33

39 25 59

94 65 82

排序之后变为：

10 14 13

25 23 33

27 25 59

39 65 73

45 94 82

最后以1步长进行排序（此时就是简单的插入排序了）。

C代码如下：

// Completed on 2014.10.10 12:00

// Language: C99

// 版权所有（C）codingwu (mail: oskernel@126.com) 

// 博客地址：http://www.cnblogs.com/archimedes/

#include stdio.h 

#include stdio.h 

void shellsort(int *a, int n)

 int i, j, k, t;

 k = n / 2;

 while(k 0)

 for(i = k; i i++){

 t = a[i];

 j = i - k;

 while(j = 0 t a[j]) {

 a[j + k] = a[j];

 j = j - k;

 a[j + k] = t;

 k /= 2;

int main()

 int a[] = {8,10,3,5,7,4,6,1,9,2};

 int N;

 N = sizeof(a) / sizeof(a[0]);

 shellsort(a, N);

 for(int k = 0; k k++)

 printf("a[%d] = %d\n",k,a[k]);

 return 0;

}

【算法】希尔排序算法 希尔排序是一种基于插入排序而改进的一种排序算法。插入排序对于近乎有序的序列，排序效率非常高，可以达到线性排序的效率。但对于其他的情况，每次只能移动一位的插入排序效率是非常低的，基于次产生了希尔排序。
Go 实现希尔排序算法及图解 本文对希尔排序进行简单的介绍，然后通过图解演示希尔排序的整个排序过程，最后使用 Go 语言实现希尔排序算法。对于希尔排序里的增量，本文首次去数组长度的一般作为增量值，然后依次减半，直到等于 1；除了这种取值方式，还可以使用 Knuth序列算法去计算增量的值。
算法之排序5——希尔排序 依次比较待插入元素 i 和分组内另一个元素，就需要用到for循环语句；当h = 5 时，a[5]恰好是数组内第6个元素，也就是第一个待插入的元素，所以初始条件是 i = h，待插入的最后一个元素就是数组内最后一个元素，即终止条件为 i a.length
【算法基础】希尔排序解析 希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时，再对全体记录进行依次直接插入排序。
希尔排序算法 希尔排序(Shell s Sort)是插入排序的一种又称 缩小增量排序 （Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。