希尔排序属于插入类排序，是将整个无序数列分割成若干小的子序列分别进行插入排序的一种方法。该方法实质上是一种分组插入方法。

希尔排序的过程是这样的：假设共有n个数，首先取增量d=n/2，将所有相隔距离为d的倍数的元素进行比较排序，然后改变增量，取d=d/2，重复上述分组和排序，直至增量d=1。进行一次比较排序后，所有元素将正确排好序。当增量d=1时，是相邻两个元素的比较排序。

例如：int a[]={10，2，4，1，6，3，5，8，7，9}；

第1次：取间隔d=n/2，间隔值d为5，因此有a[0]与a[5]，a[1]与a[6]，a[2]与a[7]……两两排序；

排序后的结果：

第2次：间隔d/=2，取d=2，有a[0]与a[2]，a[1]与a[3]，a[2]与a[5]……两两排序；

排序后的结果：

第3次：间隔为1，a[0]与a[1]，a[1]与a[2]……两两排序；(www.daowen.com)

最后结果：

希尔排序使用增量的方法，让元素可以大跨度地移动，而不是一个一个地往前移，经过很少次数的移动后，数组会变成若干个小的基本有序的数组，到最后增量减为1的时候，每个元素只要相邻位置的移动就可以了。和插入法排序相比较，元素移动的间隔和次数要少，排序效率相对比较高。

【例9-23】使用希尔排序法进行排序。

程序思路：程序通过几个方面进行控制，最外层循环确定增量，间距d最初值为元素个数的一半d=n/2，每次间隔减少一半，d=d/2，直到d等于1为止。第2层循环是将所有间隔为d的元素作为一个子序列，第3层循环将同一子序列的元素进行插入排序。

程序运行结果：（略，结果同例9-19）

如果在程序中的语句行d=d/2；前面加入以下代码，可以查看到排序过程：

程序运行结果：