希尔排序-白红宇

希尔排序

阅读量：5945 次

发布时间：2019-06-19

本文共 2964 字，大约阅读时间需要 9 分钟。

基本思想

希尔排序是基于插入排序的，又叫缩小增量排序。

在插入排序中，标记符左边的元素是有序的，右边的是没有排过序的，这个取出标记符所指向的数据，存入一个临时变量，接着，在左边有序的数组中找到临时变量应该插入的位置，然后将插入位置之后的元素依次后移一位，最后插入临时变量中的数据。

试想，假如有一个很小的数据项在靠近右端的位置上，把这个数据项插入到有序数组中时，将会有大量的中间数据项需要右移一位，这个步骤对每一个数据项都执行了将近N次复制。虽然不是所有数据项都必须移动N个位置，但是，数据项平均移动了N/2个位置，一共N个元素，总共是N²/2次复制，这实际上是一个很耗时的过程，希尔排序就是对这一步骤进行了改进，不必一个个的移动所有中间数据项，就能把较小的数据项移动到左边，大大提高了排序效率。

希尔排序通过加大插入排序时元素之间的间隔，并对这些间隔的元素进行插入排序，从而使数据能大跨度地移动。数据项之间的间隔被称为增量，习惯上还用h表示。

下图表示的是增量为4时对10个数据项进行第一轮希尔排序的过程：

此时，数据已经基本有序，所有元素离它在最终有序序列中的位置相差都不超过2个单元，通过创建这种交错的内部有序的数据项集合，把完成排序所需的工作量降到了最小，这也是希尔排序的精髓所在。

在用实现希尔排序之前，还有一个问题需要弄清楚，就是这个增量该怎么选择？

最简单的方法是第一轮排序的间隔为N/2，第二趟排序的间隔为N/4，依次类推。但是，实践证明，这种方法有时会使运行时间降到O(N²)，并不比插入排序的效率更高。

保持间隔序列中的数字互质很重要，也就是说，除了1之外它们没有公约数。简单地取间隔为N/2，N/4，N/8...1时，没有遵循这一约束，所以使希尔排序的效率降低。

有很多种有效地生成间隔序列的方法，本文提供一种，下一节的java代码也是按照这种方法来生成间隔序列的。

这种序列生成方法是由Donald Knuth(可以百度一下，图灵奖获得者，一位计算机领域的大牛)提出来的。

数列以逆向的形式从1开始，通过递归表达式：

h=3*h+1

来产生后面的间隔。

比如，我们有1000个数据项需要排序，利用h=3*h+1产生的间隔序列为：1,4,13,40,12,121,364,1093,3280...

第八个数1093显然超出了要排序的元素总数，所以第一轮排序，应该选取的间隔为364，第二轮为121，第三轮为12……

java实现

[java]

//希尔排序

public void shellSort(){

int len = array.length;

int counter = 1;

int h = 1;

while(3*h+1<len){ //确定第一轮排序时的间隔

h = 3*h+1;

}

while(h>0){

for(int i=0;i<h;i++){

shellInsertSort(i,h); //对间隔为h的元素进行插入排序

}

h = (h-1)/3; //下一轮排序的间隔

System.out.print("第"+counter+"轮排序结果：");

display();

counter++;

}

}

* 希尔排序内部使用的插入排序:

* 需要进行插入排序的元素为array[beginIndex]、array[beginIndex+increment]、array[beginIndex+2*increment]...

*@param beginIndex 起始下标

*@param increment 增量

private void shellInsertSort(int beginIndex,int increment){

int targetIndex =beginIndex+increment; //欲插入元素的下标

while(targetIndex<array.length){

int temp =array[targetIndex];

int previousIndex =targetIndex - increment; //前一个元素下标，间隔为increment

while(previousIndex>=0&&array[previousIndex]>temp){

array[previousIndex+increment]= array[previousIndex]; //比欲插入数据项大的元素后移一位

previousIndex =previousIndex - increment;

}

array[previousIndex+increment]= temp; //插入到合适的位置

targetIndex =targetIndex+increment; //插入下一个元素

}

}

//希尔排序      public void shellSort(){                         int len = array.length;             int counter = 1;                         int h = 1;             while(3*h+1
    
     0){                    for(int i=0;i
     
      =0&&array[previousIndex]>temp){                           array[previousIndex+increment]= array[previousIndex];  //比欲插入数据项大的元素后移一位                           previousIndex =previousIndex - increment;                    }                    array[previousIndex+increment]= temp;  //插入到合适的位置                                                            targetIndex =targetIndex+increment;  //插入下一个元素             }                  }