Java知网

  • 首页
  • Spring Boot
  • 面试精选
  • 程序人生
  • 资源
  • 友链
  • 关于我
  1. 首页
  2. Java
  3. 正文

三分钟彻底理解希尔排序

2021年5月2日 364点热度 0人点赞 0条评论

基本思想:希尔排序是把序列按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量的逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个序列恰好被分为一组,算法便终止。

算法实现:希尔排序需要定义一个增量,这里选择增量为gap=length/2,缩小增量以gap=gap/2的方式,这个增量可以用一个序列来表示,{n/2,(n/2)/2....1},称为增量序列,这个增量是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。

  1. 对于一个无序序列{8,9,1,7,2,3,5,4,6,0}来说,我们初始增量为gap=length/2=5,所以这个序列要被分为5组,分别是{8,3},{9,5},{1,4},{7,6},{2,0},对这5组分别进行直接插入排序,则小的元素就被调换到了前面,然后再缩小增量gap=gap/2=2。

  1. 上面缩小完增量后,序列再次被分为2组,分别是{3,1,0,9,7}和{5,6,8,4,2},再对这两组进行直接插入排序,那么序列就更加有序了。

  1. 然后再缩小增量gap=gap/2=1,这时整个序列就被分为一组即{0,2,1,4,3,5,7,6,9,8},最后再进行调整,就得到了有序序列{0,1,2,3,4,5,6,7,8,9}。

代码实现:

void ShellSort(int *arr,int len){
    for (int gap = len/2;gap > 0;gap = gap/2){
        for (int i = gap;i < len;i++){
            int j = i;
            while (j - gap >= 0 && arr[j] < arr[j - gap]){
                Swap(arr,j,j - gap);
                j = j - gap;
            }
        }
    }
}
作者:RainySouL1994
来源:https://blog.csdn.net/qq_33289077/article/details/90370899

相关文章:

  1. 三分钟彻底理解快速排序
  2. 三分钟彻底理解堆排序
标签: 排序算法
最后更新:2021年9月4日

javatip

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

文章评论

取消回复
搜一搜
扫一扫
    关注公众号
  • 技术干货推送
  • 免费资料领取
  • 定时福利发放
分类
  • Java / 110篇
  • Mysql / 17篇
  • Redis / 10篇
  • Spring Boot / 29篇
  • Spring Cloud / 16篇
  • 消息队列 / 14篇
  • 程序人生 / 21篇
  • 资源 / 4篇
  • 面试 / 23篇
归档
  • 2022年7月 / 1篇
  • 2022年4月 / 1篇
  • 2022年1月 / 1篇
  • 2021年12月 / 9篇
  • 2021年11月 / 2篇
  • 2021年9月 / 10篇
  • 2021年8月 / 4篇
  • 2021年7月 / 2篇
  • 2021年6月 / 10篇
  • 2021年5月 / 18篇
  • 2021年4月 / 75篇
  • 2021年3月 / 78篇

COPYRIGHT © 2021 javatip.cn. ALL RIGHTS RESERVED.

陇ICP备19004310号-2

甘公网安备 62010202003150号