个人中心
gpt4 book ai didi

Java经典排序算法之希尔排序详解

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java经典排序算法之希尔排序详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

1、希尔排序(Shell Sort) 。

希尔排序（Shell Sort）是一种插入排序算法，因D.L.Shell于1959年提出而得名。 Shell排序又称作缩小增量排序.

2、希尔排序的基本思想 。

希尔排序的中心思想就是：将数据进行分组，然后对每一组数据进行排序，在每一组数据都有序之后，就可以对所有的分组利用插入排序进行最后一次排序。这样可以显著减少交换的次数，以达到加快排序速度的目的。     。

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

该方法实质上是一种分组插入方法.

shell排序的算法实现

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ShellPass(SeqList R， int d)
  { //希尔排序中的一趟排序，d为当前增量
   for (i=d+ 1 ;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区
   if (R[i].key<R[i-d].key){
    R[ 0 ]=R[i];j=i-d； //R[0]只是暂存单元，不是哨兵
    do { //查找R[i]的插入位置
    R[j+d]；=R[j]； //后移记录
    j=j-d； //查找前一记录
    } while (j> 0 &&R[ 0 ].key<R[j].key)；
    R[j+d]=R[ 0 ]； //插入R[i]到正确的位置上
   } //endif
  } //ShellPass
void ShellSort(SeqList R)
  {
  int increment=n； //增量初值，不妨设n>0
  do {
    increment=increment/ 3 + 1 ； //求下一增量
    ShellPass(R，increment)； //一趟增量为increment的Shell插入排序
   } while (increment> 1 )
  } //ShellSort

注意:

当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界.

3、希尔排序算法分析 。

1、增量序列的选择.

Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下： a.最后一个增量必须为1。 b.应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况.

有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间.

2、Shell排序的时间性能优于直接插入排序.

希尔排序的时间性能优于直接排序的原因如下： a.当文件初态基本有序时，直接插入排序所需的比较和移动次数均较少。 b.当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大。 c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进.

3、稳定性 。

希尔排序是不稳定的.

4、算法演练 。

假定待排序文件由10个记录，其关键字分别是：40、38、65、97、76、13、27、49、55、04。 增量序列取值依次为：5、3、1 排序过程演示如下图所示:

Java经典排序算法之希尔排序详解

其动画效果如下面的gif动画所示:

Java经典排序算法之希尔排序详解

ps:读者也可以自己打开下面的链接，自己设定要排序的数组，进行排序演练 希尔排序动画演示 。

5、代码实现 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class ShellSortTest {
  private static void shellSort( int [] source) {
   int j;
   for ( int gap = source.length / 2 ; gap > 0 ; gap /= 2 ) {
    for ( int i = gap; i < source.length; i++) {
     int temp = source[i];
     for (j = i; j >= gap && temp < source[j - gap]; j -= gap)
      source[j] = source[j - gap];
     source[j] = temp;
    }
    System.out.print( "增长序列：" + gap + " :" );
    printArray(source);
   }
  }
 
  private static void printArray( int [] source) {
   for ( int i = 0 ; i < source.length; i++) {
    System.out.print( "\t" + source[i]);
   }
   System.out.println();
  }
 
  public static void main(String[] args) {
   int source[] = new int [] { 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 , 55 , 04 };
   System.out.print( "原始序列：" );
   printArray(source);
   System.out.println( "" );
 
   shellSort(source);
 
   System.out.print( "\n\n最后结果：" );
   printArray(source);
  }
 
}

运行结果为:

?
1
2
3
4
5
6
7
8
原始序列： 49 38 65 97 76 13 27 49 55 4
 
增长序列： 5 : 13 27 49 55 4 49 38 65 97 76
增长序列： 2 : 4 27 13 49 38 55 49 65 97 76
增长序列： 1 : 4 13 27 38 49 49 55 65 76 97
 
 
最后结果： 4 13 27 38 49 49 55 65 76 97

发现增长序列是5,2,1  和题目要求的5,3,1不同。通过分析要排序的文件由10个记录，10/2=5,5-2=3,3-2=1。刚好符合要求，因此将上面的代码稍作修改即可改变增长序列的值.

将shellSort(int[] source) 方法里的下面这行代码 。

for (int gap = source.length / 2; gap > 0; gap /= 2) {  改为： for (int gap = source.length / 2; gap > 0; gap -= 2) {  然后重新运行程序，打印结果如下:

?
1
2
3
4
5
6
7
8
原始序列： 49 38 65 97 76 13 27 49 55 4
 
增长序列： 5 : 13 27 49 55 4 49 38 65 97 76
增长序列： 3 : 13 4 49 38 27 49 55 65 97 76
增长序列： 1 : 4 13 27 38 49 49 55 65 76 97
 
 
最后结果： 4 13 27 38 49 49 55 65 76 97

如果想使用指定的增长序列来对指定的数组进行希尔排序，可以对上面的程序修改，修改后代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
public class ShellSortTest2 {
  /**
   * 待排序的数组
   */
  private int [] sources;
  /**
   * 数组内元素个数
   */
  private int itemsNum;
  /**
   * 增量数组序列
   */
  private int [] intervalSequence;
 
  /**
   * @param maxItems
   *   数组大小
   * @param intervalSequence
   *   增量数组序列
   */
  public ShellSortTest2( int [] source, int [] intervalSequence) {
   this .sources = new int [source.length];
   this .itemsNum = 0 ; // 还没有元素
   this .intervalSequence = intervalSequence;
  }
 
  /**
   * 希尔排序算法
   */
  public void shellSort() {
   int gap = 0 ; // 为增量
   for ( int iIntervalLength = 0 ; iIntervalLength < intervalSequence.length; iIntervalLength++) // 最外层循环，由增量序列元素个数决定
   {
    gap = intervalSequence[iIntervalLength]; // 从增量数组序列取出相应的增长序列
    int innerArraySize; // 每次内部插入排序的元素个数
    if ( 0 == itemsNum % gap) {
     innerArraySize = itemsNum / gap;
    } else {
     innerArraySize = itemsNum / gap + 1 ;
    }
    for ( int i = 0 ; i < gap; i++) {
     int temp = 0 ;
     int out = 0 , in = 0 ;
     if (i + (innerArraySize - 1 ) * gap >= itemsNum) {
      innerArraySize--;
     }
     // 内部用插入排序
     for ( int j = 1 ; j < innerArraySize; j++) {
      out = i + j * gap;
      temp = sources[out];
      in = out;
      while (in > gap - 1 && sources[in - gap] > temp) {
       sources[in] = sources[in - gap];
       in = in - gap;
      }
      sources[in] = temp;
     }
    }
    System.out.print( "增长序列为: " + gap + " " );
    this .displayArray();
   }
  }
 
  /**
   * 初始化待排序数组
   */
  public void initArray( int [] array) {
   for ( int i = 0 ; i < array.length; i++) {
    sources[i] = array[i];
   }
   itemsNum = array.length;
  }
 
  /**
   * 显示数组内容
   */
  public void displayArray() {
   for ( int i = 0 ; i < itemsNum; i++) {
    System.out.print( "\t" + sources[i] + " " );
   }
   System.out.println( "\n" );
  }
 
  public static void main(String[] args) {
   int [] intervalSequence = { 5 , 3 , 1 };
   int [] source = { 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 , 55 , 04 };
   ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence);
   // 初始化待排序数组
   ss.initArray(source);
   System.out.print( "原始序列： " );
   ss.displayArray();
   // 希尔排序
   ss.shellSort();
 
   System.out.print( "最后结果： " );
   ss.displayArray();
  }
}

运行结果如下:

?
1
2
3
4
5
6
7
8
9
原始序列： 49 38 65 97 76 13 27 49 55 4
 
增长序列为: 5 13 27 49 55 4 49 38 65 97 76
 
增长序列为: 3 13 4 49 38 27 49 55 65 97 76
 
增长序列为: 1 4 13 27 38 49 49 55 65 76 97
 
最后结果： 4 13 27 38 49 49 55 65 76 97

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

原文链接：http://blog.csdn.net/ouyang_peng/article/details/46554099 。

最后此篇关于Java经典排序算法之希尔排序详解的文章就讲到这里了,如果你想了解更多关于Java经典排序算法之希尔排序详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： MongoDB多表关联查询操作实例详解
文章推荐： 面向对象和面向过程的区别(动力节点java学院整理)
文章推荐： java web监听器统计在线用户及人数
文章推荐： express使用Mongoose连接MongoDB操作示例【附源码下载】
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com