前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【图解】希尔排序

【图解】希尔排序

作者头像
MickyInvQ
发布2022-09-08 12:20:38
1850
发布2022-09-08 12:20:38
举报
文章被收录于专栏:InvQ的专栏

插入排序的升级版本, 希尔排序的时间复杂度分析: 希尔排序的时间复杂度为O(n^1.5),要好于插入排序的O(n ^ 2),由于记录跳跃式的移动,希尔排序并不是一种稳定的排序方法

代码语言:javascript
复制
 private static void shellSort(int[] arr) {
        int length = arr.length;
        //进行分组,最开始时的增量(gap)为数组的一半
        for (int gap = length / 2; gap > 0; gap /= 2) {
            //对各个分组进行插入排序
            for (int i = gap; i < length; i++) {
                insertI(arr, gap, i);
            }
        }
    }

    /**
     * 将arr[i]插入到所在分组的正确位置上
     * arr[i]所在分组为:
     * ... arr[i-2gap],arr[i-gap],arr[i],arr[i+gap],arr[i+2gap]...
     */
    private static void insertI(int[] arr, int gap, int i) {
        int inserted = arr[i];
        int j;
        //插入的时候按组进行插入,组内元素两两相隔gap
        for (j = i - gap; j >= 0 && inserted < arr[j]; j -= gap) {
            arr[j + gap] = arr[j];
        }
        arr[j + gap] = inserted;
    }
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-07-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档