算法最简单之希尔算法

清疚 2022-09-24 12:30 134阅读 0赞

公共函数：

less：

public static boolean less(Comparable v , Comparable w){
    	return v.compareTo(w) < 0;
    }

exch：

public static void exch(Comparable[] a, int i ,int j){
    	Comparable t = a[i];
    	a[i] = a[j];
    	a[j] = t;
    }

概念：

希尔排序就是把数据以一定的间隔进行分组，并且对每个组进行排序。间隔一直到1为止，例如首先是间隔6，通过间隔计算，之后间隔是3，在之后就是间隔为1。

![20160731201503353][]

每次间隔怎么算的？

上图中间隔就是每一次都把间隔缩小1/2，第一次是6，第二次是3，以此来类推。

这个没有硬性要求，也可以每次缩小1/3，9、3、1 这样去间隔

希尔排序代码：

public class Shell{
        public static void sort(Comparable[] a){
            //将a[]按升序排序
            int N = a.length;
            int h = N/2;
            while(h >= 1){
                for(int i = h ; i < N; i++){
                    for(int j = i; j >= h && less(a[j] , a[j - h]); j -= h){
                        exch(a , j , j-h);
                    }
                }
                h = h/2;
            }
        }
    }

下图是上面代码，间距是一半的时候的执行步骤：

![20160731210916852][]

[20160731201503353]: /images/20220719/536054ddcff14941b75cea1b5976f5a7.png
[20160731210916852]: /images/20220719/c51e91326b48402395f7b9650a448495.png

发表评论取消回复

表情：

评论列表（有 0 条评论，134人围观）

还没有评论，来说两句吧...

相关阅读

相关 python 算法希尔算法

nums=[9,3,5,8,2,7,1] step=len(nums)//2 分组用//取整 while step>0: //退出循环条件

青旅半醒/ 2023年02月18日 14:05/ 0 赞/ 6 阅读

相关排序算法之希尔排序

\[插入排序-希尔排序\] 前言(不重要)：希尔排序是希尔这个人提出的，又名缩小增量排序，是改进版的插入排序 1.算法思想优先比较距离远的元素，将数组元素拆分

客官°小女子只卖身不卖艺/ 2022年12月29日 16:21/ 0 赞/ 211 阅读

相关排序算法之希尔排序

> 希尔排序。 > 设置一个偏移量，使用插入排序将间隔为偏移量的数组进行排序。每次排序结束后将偏移量缩小一倍，递归上述方法。 > 三重循环： >

￡神魔★判官ぃ/ 2022年11月02日 11:53/ 0 赞/ 191 阅读

相关排序算法之希尔排序

同样的先上这张图 ![Center][] 下面分析希尔插入排序：希尔排序将序列根据增量d分成几个子序列，对每个子序列作插入排序。然后把增量d变为d/2，重复这个过

清疚/ 2022年09月25日 15:23/ 0 赞/ 202 阅读

相关算法最简单之希尔算法

公共函数： less： public static boolean less(Comparable v , Comparable w){ return v

清疚/ 2022年09月24日 12:30/ 0 赞/ 135 阅读

相关算法之希尔排序

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然

- 日理万妓/ 2022年08月21日 14:49/ 0 赞/ 177 阅读

相关排序算法之希尔排序

排序算法之希尔排序这一系列主要讲的是排序算法，首先会简单介绍各种排序算法的基本思想，然后会给出每种算法的Python实现和C++实现,代码中均有非常详细的注释。最后会给

快来打我*/ 2022年08月21日 01:05/ 0 赞/ 188 阅读

相关排序算法之希尔排序

问题描述：输入一个原始数列，把它进行升序排序，从小到大输出。例如：给定数列如下： 5 15 99 45 12 1 90 19 33 41 排序后的结果为： 1

怼烎@/ 2022年06月16日 08:40/ 0 赞/ 261 阅读

相关白话算法之希尔排序

> 算法第四版读书笔记 > > 页码：P162（想看原书是怎么讲的，可自行去翻看） > > 作者：淮左白衣（还是一个少年呵，可惜终将步入油腻的中年啊）

刺骨的言语ヽ痛彻心扉/ 2022年05月28日 07:07/ 0 赞/ 186 阅读

相关 [算法]希尔算法

希尔算法是插入排序与冒泡的一种延伸,将以步长为2将数组拆分grap= length/2 查分成一小块进行排序然后继续grap/2 继续上述排序使数组大致上有序

╰半夏微凉°/ 2022年05月11日 09:34/ 0 赞/ 152 阅读