希尔（Shell）排序法

冒泡排序法、快速排序法、简单选择排序法、堆排序法等排序算法的思路较直观，但这些排序的效率比较低。如 果有大量的数据需要排序时，往往需要寻求其他更高效的排序算法，希尔（Shell）排序法便是其中一种。

希尔排序又称为缩小增量排序，该排序方法也属于插入排序类的算法，是对直接插入排序的一种改进。

算法描述

对于直接插入排序法，如果数据原来就已经按要求的顺序排列，则在排序过程中不需要进行数据移动操作，即可 得到有序数列。但是，如果最初的数据是按倒序排列的，则在进行插入排序时每次的比较都需要向后移动数据，这样，将导致算 法的效率很低。 也就是说，如果在进行直接插入排序时，数据已经是基本有序的，则排序的效率就可大大提高。另外，对于数量较小的序列 使用直接插入排序，因需要移动的数据量较少，其效率也较高。 针对这两个特点，对直接插入排序进行改进，就得到了希尔排序算法。

希尔排序的基本思想就是： 

（1）将有n个元素的数组分成n/2个数字序列，第1个数据和第n/2+1个数据为一对……以此类推。 

（2）每循环一次就将每个序列对排好顺序。 

（3）再变成n/4个序列，再次排序。 

（4）不断重复上述过程，随着序列减少，序列数最后变成1个，也就完成了整个排序。 

注意 在希尔排序中首先要解决的是怎样划分子序列。对于子序列的构成不是简单地分段，而是采取将相隔某个增量的数 据组成一个序列。一般选择增量的规则是：取上一个增量的一半作为此次子序列划分的增量，一般初始值取元素的总数量。

例如，有10个数据，可使增量为5，则序号1、5为一个子序列，2、6为一个子序列……对这些子序列排序后，再缩小增量， 重新划分子序列进行排序，直到增量为1时结束排序过程。 

下面以一组待排序的数据演示希尔排序的过程，假设有8个需要排序的数据序列如下：

 69，65，90，37，92，6，28，54

使用希尔排序法进行排序的过程如上图所示，具体排序过程如下： 

（1）首先使用元素总数量的一半（值为4）作为增量，将数据划分为4个子序列。对这4个序列分别进行排序，其中第2、6和 第3、7子序列需要进行数据交换。交换后得到第1遍排序的结果。 

（2）接着将增加缩小一半（值为2）重新划分子序列，得到两个子序列。对这两个子序列分别进行排序，得到第2遍排序后 的结果。 

（3）再次缩小增量（值为1），此时所有数据构成1个序列，对该序列使用直接插入排序，得到最后排序结果。

 在上图所示的排序过程中，

第1遍排序进行了两次数据交换（65与6交换、90与28交换），

第2次排序进行了3次数据交换 （69与28交换、90与92交换、65与54交换），

最后一遍进行了7次数据交换（不再列出，读者可去分析），一共需交换数据12 次。

如果不使用希尔排序，而使用直接插入排序对原数据进行排序，则需要进行19次数据交换，算法的效率大大降低。

由此可见，使用希排序法可显著地减少数据交换的次数，从而提高排序的效率。

提示 以上例子中只使用了8个数据，需排序的数据量越大，越能体现出希尔排序算法的效率。