shenxian32 2021-12-16 09:20 采纳率: 89.7%
浏览 26
已结题

希尔排序的数据分组是如何实现的?

问题遇到的现象和发生背景
问题相关代码,请勿粘贴截图
for (int i = gap; i < arr.length; i++) 还是没想明白这个循环为什么能给数据分组??假设数组的长度为10当gap为2时这个循环需要执行8次代表着什么??
运行结果及报错内容
我的解答思路和尝试过的方法
我想要达到的结果

    public static void shell1(int[]arr){
        int temp=0;
        //根据前面的逐步分析,使用循环处理
        //增量gap,并逐步的缩小增量
        for(int gap=arr.length/2;gap>0; gap/=2){
        //从第gap个元素,逐个对其所在的组进行直接插入
            for (int i = gap; i < arr.length; i++) {
               int j=i;
               temp=arr[j];
               //if(arr[j]<arr[j-gap]){
                   while (j-gap>=0&&temp<arr[j-gap]){
                       //移动
                       arr[j]=arr[j-gap];
                       j-=gap;
                   }//当退出while循环后,就给temp找到了插入的位置
                   arr[j]=temp;
               }
            //}
        }


        System.out.println(Arrays.toString(arr));
    }

  • 写回答

1条回答 默认 最新

  • 英雄哪里出来 2021年博客之星Top1 2021-12-16 09:25
    关注

    三、🔆动图演示

    • 初始情况下的数据如 图二-1-1 所示,基本属于乱序,纯随机出来的数据。

    在这里插入图片描述

    图二-1-1

    2、算法演示

      接下来,我们来看下排序过程的动画演示,总共分为三趟。如 图二-2-1 所示:

    图二-2-1

      一下子看完不是很理解,没有关系,我们把这几个过程分拆开来。

    3、动图分解

      第一趟分解后,如 图二-2-2 所示:

    图二-2-2

      增量为 4,所有元素总共分为 4 组,分别为 [8, 3][5, 7][6, 10][4, 2],同组内部分别执行插入排序,得到 [3, 8][5, 7][6, 10][2, 4](由于每组只有两个元素,所以升序的情况位置不变,降序的情况执行组内元素位置交换,抖动一下代表保持原顺序不变,有一种 "我不换 ~~ 我不换" 的意思在里面 )。

      第二趟分解后,如 图二-2-3 所示:

    在这里插入图片描述

    图二-2-3

      增量为 2,所有元素总共分为 2 组,分别为 [3, 6, 8, 10][5, 2, 7, 4],同组内部分别执行插入排序,[3, 6, 8, 10]已经升序,保持原样;[5, 2, 7, 4] 执行三次插入排序后变成 [2, 4, 5, 7]
      第三趟分解后,如 图二-2-4 所示:

    图二-2-4

      增量为 1,所有元素归为 1 组,为 [3, 2, 6, 4, 8, 5, 10, 7]。对它执行简单插入排序,执行完毕后,必然可以保证所有元素有序。

    扩展阅读

    (如果还是不明白,需要开试读可以联系我)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 2月27日
  • 已采纳回答 2月19日
  • 创建了问题 12月16日

悬赏问题

  • ¥15 python使用pulp线性优化时报错
  • ¥15 开源或低价数据中台哪个最好
  • ¥15 arduino编程出现字符串疑似覆盖现象
  • ¥15 我的b站在没有碰到屏幕的情况下偶尔会自动跳出进度条,就像在屏幕上点了一下一样,但我并没有点。而且视频进度并没有变。这可能是什么原因造成的?
  • ¥30 STK matlab python仿真
  • ¥15 关于IMageEnView 图标定位问题
  • ¥20 求解答(matlab)
  • ¥30 ffmpeg库使用过程中遇到的问题
  • ¥15 pyqt5 中python如何通过Qtwebchannel主动发消息给web前端
  • ¥15 关于HTML中title获取xml内容的问题