当前位置: 首页 > news >正文

希尔排序算法

ced485cbb11e458d81a746890b32cf3f.gif

作者:敲代码の流川枫

博客主页:流川枫的博客

专栏:和我一起学java

语录:Stay hungry stay foolish

工欲善其事必先利其器,给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧    

文章目录

1. 算法思想

2. 算法图解

3. 代码实现

4. 算法特点


插入排序算法详解

1. 算法思想

希尔排序是一种基于插入排序的快速的排序算法。简单插入排序对大规模乱序数组很慢,元素之恩那个一点一点从数组一端移动到另一端

为了解决这个问题,希尔排序改进了插入排序,称为缩小增量排序,该算法也是突破O(n*n)的第一批算法之一

主要思想是:把数据按照一定增量分组,对每组使用直接插入排序算法,然后缩小增量继续分组排序,随着增量逐渐减小,每组包含的关键词越来越多,增量减小至1时,整个数组被分为一组,再次排序,完成整个数组的排序,这个不断缩小的增量构成了增量序列

常用的增量序列有:

2. 算法图解

int[] array = {77,20,31,5,8,9,11,33,22,88,99,35};

以数组array排升序为例:

希尔排序图解

第一个增量为6,则原始数组被分为6组,组内的每个元素下标之差为6,然后对这6组进行插入排序

第二个增量为3,则第一次排序后数组被分为三组,组内每个元素之间数组下标之差为3 ,这三组分别进行插入排序

第三个增量为1,则第二次排序后数组被分为1组,进行插入排序

结果为:

至此希尔排序完成

3. 代码实现

代码:

import java.util.Arrays;

public class ShellSort {
    public int[] sortArray(int[] nums){
        int len = nums.length;
        //按增量分组后,每个分组中temp代表当前待排序数据,该元素之前的组内元素均已被排过
        //gap只用来分组的增量,会依次递减
        int currentValue,gap = len / 2;
        while(gap>0){
            for (int i = gap; i < len; i++) {
                currentValue = nums[i];
                //组内已被排序数据的索引
                int preIndex = i - gap;
                //在组内已被排序过的数据中倒序寻找合适的位置,如果当前待排序数据比比较的元素要小,
                // 则将比较的元素在组内后移一位
                while(preIndex>=0 && nums[preIndex] > currentValue){
                    nums[preIndex+gap]=nums[preIndex];
                    preIndex -= gap;
                }
                //当while循环结束时,说明找到了当前待排序数据的合适位置插入数据
                nums[preIndex+gap] = currentValue;
            }
            System.out.println("本轮增量:"+gap+"     排序后的数组:");
            PrintArray.print(nums);
            System.out.println("----------");
            gap/=2;
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] array = {77,20,31,5,8,9,11,33,22,88,99,35};
        ShellSort shellSort = new ShellSort();
        shellSort.sortArray(array);
    }
}
class PrintArray{
    public static void print(int[] nums){
        System.out.println(Arrays.toString(nums));
    }
}

4. 算法特点

时间复杂度:n和d的函数:O(n^1.25)~  O(1.6n^1.25)

空间复杂度: O(1)

希尔排序每一趟移动,移动位置较大,跳跃式地接近排序后的最终位置
增量序列必须是递减的,最后一个必须是1(对整体进行直接插入排序)
希尔排序是一种不稳定的排序方法,且不宜在链式存储结构上实现
希尔排序通过降低比较次数和移动次数来提高排序的效率

“ 本期的分享就到这里了, 记得给博主一个三连哈,你的支持是我创作的最大动力!

ced485cbb11e458d81a746890b32cf3f.gif

相关文章:

  • synchronized同步以及双重检索
  • Codeforce8.29-9.4做题笔记
  • springboot+宴会预定平台 毕业设计-附源码231718
  • python super()详解,一篇文章告诉你python的super是什么,如何使用
  • Redis 的持久化
  • 2022年中国证券行业智能投顾专题分析
  • MYSQL高可用架构之MHA实战(真实可用)
  • 【Reinforcement Learning】蒙特卡洛算法
  • SAP ABAP ADT安装说明 as 20220901
  • 计算机组成原理知识总结(八)输入/输出系统
  • springboot基于java的康泰小区物业管理系统的设计与实现毕业设计源码101926
  • java查看对象真实地址和哈希值的工具类
  • SOLIDWORKS直播课:解锁3DE协同设计平台的“云端结构设计角色”
  • 简单的 手写 服务器
  • 01 RocketMQ - NameServer 源码分析
  • 实现windows 窗体的自己画,网上摘抄的,学习了
  • 【从零开始安装kubernetes-1.7.3】2.flannel、docker以及Harbor的配置以及作用
  • Android 架构优化~MVP 架构改造
  • Angular4 模板式表单用法以及验证
  • Brief introduction of how to 'Call, Apply and Bind'
  • CoolViewPager:即刻刷新,自定义边缘效果颜色,双向自动循环,内置垂直切换效果,想要的都在这里...
  • Java深入 - 深入理解Java集合
  • Mybatis初体验
  • Node项目之评分系统(二)- 数据库设计
  • redis学习笔记(三):列表、集合、有序集合
  • SpringCloud(第 039 篇)链接Mysql数据库,通过JpaRepository编写数据库访问
  • 不用申请服务号就可以开发微信支付/支付宝/QQ钱包支付!附:直接可用的代码+demo...
  • 分布式任务队列Celery
  • 给初学者:JavaScript 中数组操作注意点
  • 更好理解的面向对象的Javascript 1 —— 动态类型和多态
  • 极限编程 (Extreme Programming) - 发布计划 (Release Planning)
  • 猫头鹰的深夜翻译:Java 2D Graphics, 简单的仿射变换
  • 悄悄地说一个bug
  • 深度学习入门:10门免费线上课程推荐
  • 通过几道题目学习二叉搜索树
  • 微服务框架lagom
  • 微信小程序开发问题汇总
  • d²y/dx²; 偏导数问题 请问f1 f2是什么意思
  • Nginx惊现漏洞 百万网站面临“拖库”风险
  • 不要一棍子打翻所有黑盒模型,其实可以让它们发挥作用 ...
  • 没有任何编程基础可以直接学习python语言吗?学会后能够做什么? ...
  • ​虚拟化系列介绍(十)
  • #每天一道面试题# 什么是MySQL的回表查询
  • $.ajax()方法详解
  • (1)(1.11) SiK Radio v2(一)
  • (react踩过的坑)Antd Select(设置了labelInValue)在FormItem中initialValue的问题
  • (分布式缓存)Redis分片集群
  • (附源码)ssm码农论坛 毕业设计 231126
  • (全部习题答案)研究生英语读写教程基础级教师用书PDF|| 研究生英语读写教程提高级教师用书PDF
  • (实战篇)如何缓存数据
  • (四) 虚拟摄像头vivi体验
  • .NET 4.0中使用内存映射文件实现进程通讯
  • .NET 使用 ILRepack 合并多个程序集(替代 ILMerge),避免引入额外的依赖
  • .net利用SQLBulkCopy进行数据库之间的大批量数据传递
  • .Net中wcf服务生成及调用