七大排序之希尔排序

简介: 希尔排序是插入排序的一种,又称为缩小增量法。其思想就是先选定一个整数 gap ,把待排序数组中间隔为 gap 的数分为一组,并对每一组内的数进行插入排序。然后,取,重复上述分组排序工作。当 gap = 1时,所有数在同一组内排好序。

时间复杂度: ~

空间复杂度:

稳定性:不稳定

1、基本思想

   希尔排序是插入排序的一种,又称为缩小增量法。其思想就是先选定一个整数 gap ,把待排序数组中间隔为 gap 的数分为一组,并对每一组内的数进行插入排序。然后,取,重复上述分组排序工作。当 gap = 1时,所有数在同一组内排好序。

2、代码讲解和实现

希尔排序实现可以分为两步:

       1:分组

       2:组内排序

① 分组

       我们首先要给 gap 取值,通常 会把数组的长度先赋值给 gap,然后以gap为步长进行分组排序。接着 gap除以2,再进行上述操作。


       最后 我们一定要把数组作为一个整体再进行排序,因为每次分组就肯能落下几个数,所以最后gap 一定要赋值为1。

② 组内排序

       组内排序跟插入排序大致相同,在插入排序中外循环是从 1下标开始进行插入,而在希尔排序中 gap 是不断变化的,所以外循环要从 gap 为下标开始,每次++,争取把每个组都遍历到。


       内循环 j 从 i - gap 开始,每次减去 gap,这样一组内的元素都趋于有序了。

 //组内插入排序
    private static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for(; j >= 0; j -= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    //分组
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);//把数组作为一个整体进行排序

3、特性总结

1.希尔排序是对直接插入排序的优化。

2.当gap > 1 时都是预排序,目的是让数组更接近有序。当 gap == 1 时,数组已经接近有序,这样就会很快。这样整体而言,可以达到优化的效果。

3.希尔排序的时间复杂度不好算,因为gap的取值方法很多,导致很难去计算,因此在很多书中给出的希尔排序时间复杂度都不固定。我们可以暂时按照~来算。

  4.希尔排序不是稳定的排序。

相关文章
|
机器学习/深度学习 算法 计算机视觉
超级干货 | 用万字文章总结25种正则化方法(值得收藏)(二)
超级干货 | 用万字文章总结25种正则化方法(值得收藏)(二)
607 0
|
7天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
9049 24
|
7天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2693 13
|
2天前
|
人工智能 安全 应用服务中间件
NGINX 爆出两处高危漏洞 可导致未经身份验证的远程代码执行
NGINX曝出两个高危漏洞(CVE-2026-123633和CVE-2026-123007),CVSS 9.2分,均属HTTP/2内存安全缺陷,无需认证即可远程执行代码。影响自2015年起的多个版本,静态站点亦受威胁。修复版本为开源版1.30.7/1.31.9。(239字)
1284 0
NGINX 爆出两处高危漏洞 可导致未经身份验证的远程代码执行
|
5天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)
|
10天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
10天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
23天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
11102 59