希尔排序算法 你的名字 2023-10-10 14:51 3阅读 0赞 ![ced485cbb11e458d81a746890b32cf3f.gif][] > 作者:敲代码の流川枫 > > 博客主页:[流川枫的博客][Link 1] > > 专栏:[和我一起学java][java] > > 语录:Stay hungry stay foolish > > 工欲善其事必先利其器,给大家介绍一款超牛的斩获大厂offer利器——牛客网 > > [点击免费注册和我一起刷题吧][Link 2] ![31270a42f5334a069f804882103f7e23.png][] **文章目录** 1. 算法思想 2. 算法图解 3. 代码实现 4. 算法特点 -------------------- [插入排序算法详解][Link 3] ## 1. 算法思想 ## > 希尔排序是一种基于插入排序的快速的排序算法。简单插入排序对大规模乱序数组很慢,元素之恩那个一点一点从数组一端移动到另一端 > 为了解决这个问题,希尔排序改进了插入排序,称为缩小增量排序,该算法也是突破O(n\*n)的第一批算法之一 > **主要思想是:把数据按照一定增量分组,对每组使用直接插入排序算法,然后缩小增量继续分组排序,随着增量逐渐减小,每组包含的关键词越来越多,增量减小至1时,整个数组被分为一组,再次排序,完成整个数组的排序,这个不断缩小的增量构成了增量序列** 常用的增量序列有: ![c6934696dc094ce2b3ea5874dbf68759.png][] ## 2. 算法图解 ## int[] array = {77,20,31,5,8,9,11,33,22,88,99,35}; 以数组array排升序为例: 希尔排序图解 ![bd7b89bdb6de4319bbb6f2a3549e93cd.png][] 第一个增量为6,则原始数组被分为6组,组内的每个元素下标之差为6,然后对这6组进行插入排序 ![cf1c9a29875c496ea42c5908fdb456d5.png][] 第二个增量为3,则第一次排序后数组被分为三组,组内每个元素之间数组下标之差为3 ,这三组分别进行插入排序 ![8ccce014584e45ee85a6a6d60396af3e.png][] 第三个增量为1,则第二次排序后数组被分为1组,进行插入排序 结果为: ![6adda6b969d44453b89d3165dba9aa1c.png][] 至此希尔排序完成 ## 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)); } } ![6f710a59660f40af82797eae77a703f0.png][] ## 4. 算法特点 ## > 时间复杂度:n和d的函数:O(n^1.25)~ O(1.6n^1.25) > > 空间复杂度: O(1) > 希尔排序每一趟移动,移动位置较大,跳跃式地接近排序后的最终位置 > 增量序列必须是递减的,最后一个必须是1(对整体进行直接插入排序) > 希尔排序是一种不稳定的排序方法,且不宜在链式存储结构上实现 > 希尔排序通过降低比较次数和移动次数来提高排序的效率 > “ 本期的分享就到这里了, 记得给博主一个三连哈,你的支持是我创作的最大动力! ![ced485cbb11e458d81a746890b32cf3f.gif][] [ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif [Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343 [java]: https://blog.csdn.net/chenchenchencl/category_11932758.html [Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c [31270a42f5334a069f804882103f7e23.png]: https://img-blog.csdnimg.cn/31270a42f5334a069f804882103f7e23.png [Link 3]: https://blog.csdn.net/chenchenchencl/article/details/126580227?spm=1001.2014.3001.5502 [c6934696dc094ce2b3ea5874dbf68759.png]: https://img-blog.csdnimg.cn/c6934696dc094ce2b3ea5874dbf68759.png [bd7b89bdb6de4319bbb6f2a3549e93cd.png]: https://img-blog.csdnimg.cn/bd7b89bdb6de4319bbb6f2a3549e93cd.png [cf1c9a29875c496ea42c5908fdb456d5.png]: https://img-blog.csdnimg.cn/cf1c9a29875c496ea42c5908fdb456d5.png [8ccce014584e45ee85a6a6d60396af3e.png]: https://img-blog.csdnimg.cn/8ccce014584e45ee85a6a6d60396af3e.png [6adda6b969d44453b89d3165dba9aa1c.png]: https://img-blog.csdnimg.cn/6adda6b969d44453b89d3165dba9aa1c.png [6f710a59660f40af82797eae77a703f0.png]: https://img-blog.csdnimg.cn/6f710a59660f40af82797eae77a703f0.png
还没有评论,来说两句吧...