请选择 进入手机版 | 继续访问电脑版

好程序员-千锋教育旗下高端IT职业教育品牌

400-811-9990
我的账户
好程序员

专注高端IT职业培训

亲爱的猿猿,欢迎!

已有账号,请

如尚未注册?

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

[复制链接]
叶子老师 发表于 2019-7-18 16:36:18 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
好程序员Java学习路线带你5分钟了解希尔排序,前言希尔排序(shell sort)是插入排序的一种,它是简单插入排序经过改进之后的一个更高效的算法,这个排序方法又称为缩小增量排序。
希尔排序思想介绍
简单来说,希尔排序是将较大的数据集合逻辑上分割成若干个小的集合,然后对每个分组分别进行插入排序。
例如,假设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。
算法说明:
待排序数据:1216741059
第一次的增量为数组元素的长度/2,即increment=4,得到四个分组:
分组一:12,             4
分组二:      1,              10
分组三:          6,                  5
分组四:             7,                    9
对这四个分组分别进行插入排序,最终得到:
4157121069
比较increment取上次值的一半,即increment=2,得到两个分组:
分组一:4,  5,  126
分组二:    17,  109
对这两个分组分别进行插入排序,最终得到:
4, 157691210
第三次比较,increment=1,即只有一个分组:
分组一:4157691210
     对其进行插入排序,最终得到:
1456791012
希尔排序的代码实现
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. }  
总结
希尔排序是插入排序的改进,但是希尔排序中使用到了多次插入排序,在不同的插入排序过程中,相同的元素在各自的插入排序中可能会移动,造成排序的稳定性被打乱,所以希尔排序是不稳定的。
好程序员官网:http://www.goodprogrammer.org

精彩内容,一键分享给更多人!
回复

使用道具 举报

您需要登录后才可以回帖

本版积分规则

关注我们
好程序员
千锋好程序员

北京校区(总部):北京市海淀区宝盛北里西区28号中关村智诚科创大厦

深圳西部硅谷校区:深圳市宝安区宝安大道5010号深圳西部硅谷B座A区605-619

杭州龙驰智慧谷校区:浙江省杭州市下沙经济技术开发区元成路199号龙驰智慧谷B座7层

郑州校区:郑州市二七区航海中路60号海为科技园C区10层、12层

Copyright 2007-2019 北京千锋互联科技有限公司 .All Right

京ICP备12003911号-5 京公安网11010802011455号

请您保持通讯畅通1对1咨询马上开启