行业资讯 2025年08月6日
0 收藏 0 点赞 982 浏览 1190 个字
摘要 :

文章目录 简介 希尔排序算法思路图解 第1步 第2步 第3步 希尔排序经典代码实现  总结 本文重点讲解Java实现希尔排序经典代码和算法思路。 简介 希尔排序是希尔(Donal……




本文重点讲解Java实现希尔排序经典代码和算法思路。

简介

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法,其也是一种特殊的插入排序,即将简单的插入排序进行改进后的一个更加高效的版本,也称缩小增量排序。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 1、插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 2、但插入排序一般来说是低效的,因为插入排序每次只能将数据移动1

希尔排序是先将整个待排序的序列分组排序(两两一组),待整个序列中基本有序时,再对全体记录进行依次直接插入排序。

希尔排序是非稳定排序算法,它通过比较相距指定步长的元素来进行排序,每趟比较的步长随着算法的进行而减小,直到步长等于1的最后一趟排序结束。

希尔排序算法思路图解

现在我们以序列: {8, 9, 1, 7, 2, 3, 5, 6, 4, 0} 为示例进行图解算法思路!

第1步

初始步长gap = length/2 = 5,意味着将整个数组分为了5组,即[8,3],[9,5],[1,6],[7,4],[2,0],对每组进行插入排序,得到序列:{3,5,1,4,0,8,9,6,7,2},可以看到:3,5,4,0这些小元素都被提到前面了。

第2步

缩小增量gap = 5/2 = 2,数组被分为两组,即[3,1,0,9,7],[5,4,8,6,2],对这两组分别进行直接插入排序,可以看到,整个数组的有序程度更进一步了。Java实现希尔排序经典代码和算法思路

第3步

再次缩小增量,gap = 2/2 = 1,此时整个数组为[0,2,1,4,3,5,7,6,9,8],进行一次插入排序,即可实现数组的有序化(仅需要简单微调,而无需大量移动操作)。Java实现希尔排序经典代码和算法思路

希尔排序经典代码实现

接下来我们看下如何通过java代码来实现经典的希尔排序吧:

    /**
     * 希尔排序
     * 时间复杂度:O(N^1.3~N^1.5)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     * @param array
     */
    public static void shellSort(int[] array) {
        int gap = array.length; ;
        while (gap > 1) {
            gap /= 2;
            shell(array, gap);
        }
    }
    private static void shell(int[] array, int gap) {
        // 从小到大排序
        if(array == null) {
            return;
        }
        int tmp = 0;
        for (int i = gap; i < array.length; i++) {
            tmp = array[i];
            for (int j = i - gap; j >= 0; j -= gap) {

                // j往后走
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                    array[j] = tmp;
                } else {
                    break;
                }
            }
        }
    }

 总结

以上就是Java实现希尔排序经典代码和算法思路的全部内容,你学会了吗?

微信扫一扫

支付宝扫一扫

版权: 转载请注明出处:https://www.zuozi.net/9712.html

管理员

相关推荐
2025-08-06

文章目录 一、Reader 接口概述 1.1 什么是 Reader 接口? 1.2 Reader 与 InputStream 的区别 1.3 …

988
2025-08-06

文章目录 一、事件溯源 (一)核心概念 (二)Kafka与Golang的优势 (三)完整代码实现 二、命令…

465
2025-08-06

文章目录 一、证明GC期间执行native函数的线程仍在运行 二、native线程操作Java对象的影响及处理方…

348
2025-08-06

文章目录 一、事务基础概念 二、MyBatis事务管理机制 (一)JDBC原生事务管理(JdbcTransaction)…

456
2025-08-06

文章目录 一、SnowFlake算法核心原理 二、SnowFlake算法工作流程详解 三、SnowFlake算法的Java代码…

517
2025-08-06

文章目录 一、本地Jar包的加载操作 二、本地Class的加载方法 三、远程Jar包的加载方式 你知道Groo…

832
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:08:00-23:00

客服QQ

122325244

客服电话

400-888-8888

客服邮箱

122325244@qq.com

扫描二维码

关注微信客服号