elva

shellsort之一

转自:
http://apps.hi.baidu.com/share/detail/15570437


基本思想

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

算法实现(Java语言)

package org.shirdrn.internal.sort;

/**
* <p><B>希尔排序算法类</B>
* <p>基本思想:
* <p>
* <p>先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的
* 倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上
* 述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行
* 直接插入排序为止。
* <p>
* <p>该方法实质上是一种分组插入方法。
*
* @author shirdrn
*
*/
public class ShellSort {

private Integer[] array;

public ShellSort(Integer[] array) {
   this.array = array;
}

public void sort() {
   int d = array.length;
   do {
    d /= 2;
    shellPass(d); // 根据逐渐减小的间隔增量,循环调用一趟排序
   }while(d>1);
}

/**
* 希尔一趟排序
*
* @param d 间隔增量
*/
private void shellPass(int d) {
   Integer tmp;
   for(int i=d; i<array.length; i++) { // 数组下标从0开始,初始i=d表示一趟排序中第二个元素
    tmp = array[i]; // array[i]的拷贝
    // 如果待处理的无序区第一个元素array[i] < 有序区最大的元素array[i-d]
    // 需要将有序区比array[i]大的元素向后移动
    if(array[i]<array[i-d]) {
     int j=i-d;
     while(j>=0 && tmp<array[j]) {
      array[j+d] = array[j]; // 将左侧有序区中元素比array[i]大的array[j+d]后移
      j -= d;
     }
     // 如果array[i] >= 左侧有序区最大的array[i-d],或者经过扫描移动后,找到一个比array[i]小的元素
     // 将右侧无序区第一个元素tmp = array[i]放到正确的位置上
     array[j+d] = tmp;
    }
   }
}

/**
* 输出数组元素
*/
public String print() {
   StringBuffer sb = new StringBuffer();
   for(int i=0; i<array.length; i++) {
    sb.append(array[i]);
    if(i != array.length-1) {
     sb.append(", ");
    }
   }
   return sb.toString();
}
}

排序过程

希尔排序的过程如下:

首先初始化间隔d为待排序数组的长度,无需排序。

减小d,对于每次得到的间隔d,执行多组排序,使得原始数组间隔为d的一个子数组为有序,该数组通过类似直接插入排序的算法来执行排序。

直到,d减小为1的时候,整个数组为有序。这里,采用二分的策略来得到间隔d。

执行希尔排序的过程示例如下:

假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49},数组大小为20。

首先,初始化d = 20。在循环中反复得到间隔d,根据d执行一趟希尔排序。

对于d = 20/2 = 10:

根据d = 10来对数组排序,将原始数组分成2块: {94,12,34,76,26,9,0,37,55,76}与{37,5,68,83,90,37,12,65,76,49},也就是对如下数组分别进行直接插入排序:

{array[0],array[10]} = {94,37}

{array[1],array[11]} = {12,5}

{array[2],array[12]} = {34,68}

{array[3],array[13]} = {76,83}

{array[4],array[14]} = {26,90}

{array[5],array[15]} = {9,37}

{array[6],array[16]} = {0,12}

{array[7],array[17]} = {37,65}

{array[8],array[18]} = {55,76}

{array[9],array[19]} = {76,49}

第一趟希尔排序后,各个子数组变为:

{37,5,34,76,26,9,0,37,55,49}与{94,12,68,83,90,37,12,65,76,76},

即:array = {37,5,34,76,26,9,0,37,55,49,94,12,68,83,90,37,12,65,76,76},

对于d = 10/2 = 5:

根据d = 5来对数组排序,将第一趟希尔排序后的数组分成4块 :{37,5,34,76,26}、{9,0,37,55,49}、{94,12,68,83,90}与{37,12,65,76,76},也就是对如下数组分别进行直接插入排序:

{array[0],array[5],array[10],array[15]} = {37,9,94,37}

{array[1],array[6],array[11],array[16]} = {5,0,12,12}

{array[2],array[7],array[12],array[17]} = {34,37,68,65}

{array[3],array[8],array[13],array[18]} = {76,55,83,76}

{array[4],array[9],array[14],array[19]} = {26,49,90,76}

第二趟希尔排序后,各个子数组变为:

{9,0,34,55,26}、{37,5,37,76,49}、{37,12,65,76,76}与{94,12,68,83,90},

即:array = {9,0,34,55,26,37,5,37,76,49,37,12,65,76,76,94,12,68,83,90}。

对于d = 5/2 = 2:

根据d = 2来对数组排序,将第二趟希尔排序后的数组分成10块: {9,0}、{34,55}、{26,37}、{5,37}、{76,49}、{37,12}、{65,76}、{76,94}、{12,68}与{83,90},也就是对如下数组分别进行直接插入排序:

{array[0],array[2],array[4],array[6],array[8],array[10],array[12],array[14],array[16],array[18]} = {9,34,26,5,76,37,65,76,12,83}

{array[1],array[3],array[5],array[7],array[9],array[11],array[13],array[15],array[17],array[19]} = {0,55,37,37,49,12,76,94,68,90}

第三趟希尔排序后,各个子数组变为:{5,0}、{9,12}、{12,37}、{26,37}、{34,49}、{37,55}、{65,68}、{76,76}、{76,90}与{83,94},

即:array = :{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}。

对于d = 2/2 = 1:

根据d = 1来对数组排序,将第二趟希尔排序后的数组分成20块:{5}、{0}、{9}、{12}、{12}、{37}、{26}、{37}、{34}、{49}、{37}、{55}、{65}、{68}、{76}、{76}、{76}、{90}、{83}、{94},也就是对如下数组分别进行直接插入排序:

{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}

第四趟希尔排序以后,数组已经有序:

array = {0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90,94}。

因为 d= 1,希尔排序结束。

测试用例

package org.shirdrn.internal.sort;

import junit.framework.TestCase;

public class TestShellSort extends TestCase {

private ShellSort sort;
private Integer[] array;

@Override
protected void setUp() throws Exception {
   array = new Integer[]{
     94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49
   };
   sort = new ShellSort(array);
}

public void testSort() {
   // B(Before),A(After)
   System.out.println("(B)Sorting : " + this.sort.print());
   this.sort.sort();
   System.out.println("(A)Sorting : " + this.sort.print());
}
}

测试结果:

(B)Sorting : 94, 12, 34, 76, 26, 9, 0, 37, 55, 76, 37, 5, 68, 83, 90, 37, 12, 65, 76, 49
(A)Sorting : 0, 5, 9, 12, 12, 26, 34, 37, 37, 37, 49, 55, 65, 68, 76, 76, 76, 83, 90, 94

算法分析

(一)时间复杂度

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征:

① 最后一个增量必须为1;

② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验,给出了目前较好的结果:当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。

(二)空间复杂度

因为希尔排序依赖于增量序列,从而导致排序的趟数不固定,对于不同的增量执行一趟希尔排序,只用到一个辅助变量。

(三)排序稳定性

通过上述元素76可以看到,希尔排序不稳定。

因此,希尔排序是不稳定的。

posted on 2010-11-01 18:06 叶子 阅读(847) 评论(0)  编辑 收藏 引用 所属分类: 数据结构


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理