ITPub博客

首页 > 应用开发 > Java > 好程序员Java学习路线带你5分钟了解希尔排序

好程序员Java学习路线带你5分钟了解希尔排序

原创 Java 作者:好程序员IT 时间:2019-07-18 17:58:02 0 删除 编辑

好程序员Java学习路线带你5分钟了解希尔排序,前言:希尔排序(shell sort)是插入排序的一种,它是简单插入排序经过改进之后的一个更高效的算法,这个排序方法又称为缩小增量排序。

希尔排序思想介绍

简单来说,希尔排序是将较大的数据集合逻辑上分割成若干个小的集合,然后对每个分组分别进行插入排序。

例如,假设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。

算法说明:

待排序数据:12,1,6,7,4,10,5,9

第一次的增量为数组元素的长度/2,即increment=4,得到四个分组:

分组一:12,             4

分组二:      1,              10

分组三:          6,                  5

分组四:             7,                    9

对这四个分组分别进行插入排序,最终得到:

4,1,5,7,12,10,6,9

第二次比较,increment取上次值的一半,即increment=2,得到两个分组:

分组一:4,  5,  12, 6

分组二:    1, 7,  10, 9

对这两个分组分别进行插入排序,最终得到:

4, 1, 5,7, 6,9,12,10

第三次比较,increment=1,即只有一个分组:

分组一:4,1,5,7,6,9,12,10

   对其进行插入排序,最终得到:

1,4,5,6,7,9,10,12

希尔排序的代码实现

1.  public   static   void  shellSort( int [] arr){  

2.      int  temp = 0;  

3.      int  j = 0;  

4.     //增量初始值是长度的一半,增量每次变为原来的一半  

5.      for ( int  inc = arr.length/2 ; inc >= 1 ; inc /= 2){  

6.          for ( int  i = inc ; i < arr.length; i++){  

7.             temp = arr ;  

8.             //将当前数与减去增量之后位置的数进行比较,如果大于,则后移  

9.              for (j = i - inc; j >=0; j -= inc){  

10.                  if (arr[j] > temp){  

11.                     arr[j + inc] = arr[j];  

12.                 } else {  

13.                      break ;  

14.                 }  

15.             }  

16.             arr[j + inc]=temp;  

17.         }  

18.     }  

19. }  

总结

希尔排序是插入排序的改进,但是希尔排序中使用到了多次插入排序,在不同的插入排序过程中,相同的元素在各自的插入排序中可能会移动,造成排序的稳定性被打乱,所以希尔排序是不稳定的。


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69913892/viewspace-2651044/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
欢迎关注公众号:好程序员特训营 web前端教程分享 723729549 大数据教程分享 703503210

注册时间:2019-03-20

  • 博文量
    428
  • 访问量
    263509