【算法学习】七希尔排序

小鱼儿 2023-07-05 13:07 8阅读 0赞

> 程序猿学社的GitHub，欢迎**Star：**  
> https://github.com/ITfqyd/cxyxs  
> 觉得有用,可以**点赞,关注,评论，留言**四连发。

### 文章目录 ###

*  前言
 *  1.背景
 *  2.什么是希尔排序？
 *  3.排序原理
 *  4. 实战
 *  5.性能分析
 *   *  时间复杂度
     *  稳定性
 *  后记

# 前言 #

> 社长，一个爱学习，爱分享的程序猿，始终相信,付出总会有回报的。知识改变命运，学习成就未来。爱拼才会赢!  
> 程序猿学社的GitHub，已整理成相关技术专刊，欢迎Star：。  
> https://github.com/ITfqyd/cxyxs

# 1.背景 #

可以先看看我的插入排序文章。  
[插入排序][Link 1]  
这里简单的描述一下插入排序，通过实际生活的小事例，我们来回顾一下插入排序。

回想起，社长当年读小学的时候，因为长度不高不矮，坐在第三排，没错，座位的位置就是为了从低到高排序的。但是不排斥某些老铁，为了坐一些小动作，本来人很矮，还要做到最后面。假设，隔壁小王最矮，而他为了躲避老师的视野，坐在最后面，通过插入排序，隔壁小王每次都得跟前面一个同学，从后开始一个个换位置，而后面的同学也得一个个后退一个位置，一直到第一个。你觉得这样的排序性能能好嘛。

**总结**插入排序在对几乎已经排好序的数据操作时，效率高

# 2.什么是希尔排序？ #

**希尔排序是插入排序的plus版本**。一个叫D.LShell的人于1959年提出。再插入排序的基础上做了一些优化。也有人称希尔排序为“缩小增量排序”。具体为什么又叫插入增量排序。别急，社长后面会一一告诉你。

**希尔排序**是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，就是一个简单的插入排序。

**稳定性**在算法学习的过程中，我们可以经常看到这个词” 稳定性”,看过社长选择排序篇的都知道，选择排序是不稳定的，冒泡排序是稳定的。 假设，社长和隔壁小王去吃饭，有一些没有素质的人，插队，插在我和隔壁老王的前面，我们认为这种情况就是稳定的，插在我和隔壁老王的中间，这种情况就是不稳定的，因为他影响了我和隔壁老王的交流，验证破坏了我和隔壁老王纯洁的友情。

# 3.排序原理 #

对于大规模的的数据，插入排序很慢，因为他只能两两交互位置。可想而知，只能搞不到那里去。假设数据长度是n，插入排序第一轮需要跑n-1次

而希尔排序的为了提高查询效率，引入了分组的概念。认为间隔k之间的数据都是有序的。如何数据长度为10。每次交换的次数，都是上一次的一半，一直交换到间隔为1为止。

**思路：**

**1.** 选择一个k,假设每次间隔缩小1半，进行分组。  
**2.** 对分为同一组的两个数，进行比较。  
**3.** 依次从k递减到k位1.这时候数据就排序好了。  
![format_png][]  
热闹的江湖，有开始蠢蠢欲动，都打算一决高下，为了减少矛盾纠纷。只好各位高手纷纷报名，为了防止其他成员，联合淘汰一些高手，这里采取蒙面PK的方式。每个人可以领取一个编号。有10个座位。代表前10。由于无法暂时无法知道谁低，先暂时随便坐。

而这是的裁判团评委，纷纷在出谋划策，看看什么样的方式，能尽快分出高低。

有人说冒泡方式,有人说插入排序这种方式，其中一个冷面老者说可以试试通过希尔排序的方式。大家觉得也没有什么好办法，只好试试。下面我们来看看，他们是如何决出高低。

**第一轮排序：**  
![format_png 1][]  
先把各路高手分为了5组，每组2个人，决出高低。失败的选手，坐到前面去，等待pk。为什么坐到前面去？那是因为高手都是低调的，喜欢坐在后面，默默的不说法。

分组名单 \[49,13\]、【38,27】、【65,13】、【97,55】、【76,4】

**第二轮排序：**  
经过第一轮的精彩pk,座位排布如下  
![format_png 2][]  
第二轮排序的规则如下。把数据分为2组。通过抽签决定，红色一组，黑色一组。

\[13,49,4,38,97\]、\[17,55,49,65,76\]

各个组内采取插入排序取代对方位置的方式，进行排序。

观看了这么多的高手对决，我们的吃瓜群众，已经能大致看出谁高谁低勒。

**第三轮排序。**

第三天发布昨天的比赛结果，结果如下  
![format_png 3][]  
直接采取上次插入排序的方式,进行pk一决高下。所有各路高手都一一pk然后，各路的高手的排名也已经出来了。排名如下，越靠前,表示越菜。低调才是王道。  
![format_png 4][]

# 4. 实战 #

package com.cxyxs.dilution.util;
    
    import java.util.Arrays;
    
    /** * Description： 希尔排序 * 转发请注明来源 程序猿学社 - https://ithub.blog.csdn.net/ * Author: 程序猿学社 * Date: 2020/2/10 23:23 * Modified By: */
    public class ShellSortUtils { 
        public static void main(String[] args) { 
            int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
            System.out.println("原数据:" + Arrays.toString(arr));
            shellSort(arr);
            System.out.println("排序完:" + Arrays.toString(arr));
        }
    
        /** * 希尔排序 * @param arr */
        private static void shellSort(int[] arr) { 
            //进行分组，每次为之前的一半
            int index=1;
            for (int gap = arr.length/2; gap > 0 ; gap/=2) { 
                System.out.println("第"+index+"次排序");
                //使用插入排序
                for (int i = gap; i < arr.length; i++) { 
                   int j=i;
                   int temp = arr[j];
                  if(temp < arr[j -gap]){ 
                      //j-gap>=0，就是应为步进为gap,最后那次刚好为0
                       while (j -gap>= 0 && temp < arr[j -gap]){ 
                            arr[j] = arr[j-gap];
                            j -= gap;
                        }
                   }
    //给temp找到对应的位置
                   arr[j] = temp;
                }
                System.out.println("排序后:"+Arrays.toString(arr));
                index++;
                System.out.println();
            }
        }
    }
    测试结果：
    通过代码详细打印出来，以方便理解。

原数据:\[49, 38, 65, 97, 76, 13, 27, 49, 55, 4\]

**第1次排序**  
索引5,值13,步进5,\[49, 38, 65, 97, 76, 13, 27, 49, 55, 4\]  
当前值：13,上一个步进：49

索引6,值27,步进5,\[13, 38, 65, 97, 76, 49, 27, 49, 55, 4\]  
当前值：27,上一个步进：38

索引7,值49,步进5,\[13, 27, 65, 97, 76, 49, 38, 49, 55, 4\]  
当前值：49,上一个步进：65

索引8,值55,步进5,\[13, 27, 49, 97, 76, 49, 38, 65, 55, 4\]  
当前值：55,上一个步进：97

索引9,值4,步进5,\[13, 27, 49, 55, 76, 49, 38, 65, 97, 4\]  
当前值：4,上一个步进：76

排序后:\[13, 27, 49, 55, 4, 49, 38, 65, 97, 76\]

**第2次排序**

索引2,值49,步进2,\[13, 27, 49, 55, 4, 49, 38, 65, 97, 76\]  
索引3,值55,步进2,\[13, 27, 49, 55, 4, 49, 38, 65, 97, 76\]  
索引4,值4,步进2,\[13, 27, 49, 55, 4, 49, 38, 65, 97, 76\]  
当前值：4,上一个步进：49  
当前值：4,上一个步进：13  
索引5,值49,步进2,\[4, 27, 13, 55, 49, 49, 38, 65, 97, 76\]  
当前值：49,上一个步进：55  
索引6,值38,步进2,\[4, 27, 13, 49, 49, 55, 38, 65, 97, 76\]  
当前值：38,上一个步进：49  
索引7,值65,步进2,\[4, 27, 13, 49, 38, 55, 49, 65, 97, 76\]  
索引8,值97,步进2,\[4, 27, 13, 49, 38, 55, 49, 65, 97, 76\]  
索引9,值76,步进2,\[4, 27, 13, 49, 38, 55, 49, 65, 97, 76\]  
排序后:\[4, 27, 13, 49, 38, 55, 49, 65, 97, 76\]

**第3次排序**

索引1,值27,步进1,\[4, 27, 13, 49, 38, 55, 49, 65, 97, 76\]

索引2,值13,步进1,\[4, 27, 13, 49, 38, 55, 49, 65, 97, 76\]

当前值：13,上一个步进：27

索引3,值49,步进1,\[4, 13, 27, 49, 38, 55, 49, 65, 97, 76\]

索引4,值38,步进1,\[4, 13, 27, 49, 38, 55, 49, 65, 97, 76\]

当前值：38,上一个步进：49

索引5,值55,步进1,\[4, 13, 27, 38, 49, 55, 49, 65, 97, 76\]

索引6,值49,步进1,\[4, 13, 27, 38, 49, 55, 49, 65, 97, 76\]

当前值：49,上一个步进：55

索引7,值65,步进1,\[4, 13, 27, 38, 49, 49, 55, 65, 97, 76\]

索引8,值97,步进1,\[4, 13, 27, 38, 49, 49, 55, 65, 97, 76\]

索引9,值76,步进1,\[4, 13, 27, 38, 49, 49, 55, 65, 97, 76\]

当前值：76,上一个步进：97

排序后:\[4, 13, 27, 38, 49, 49, 55, 65, 76, 97\]

排序完:\[4, 13, 27, 38, 49, 49, 55, 65, 76, 97\]

# 5.性能分析 #

最近有社友在问，为什么他写的希尔排序通过大数据模拟测试，发现性能还没有插入排序快？  
这是因为他可能用的是**交换式**(只要有符合后移的条件，就后移)的方式。  
本文介绍的是\*\*移位式(**通过中间变量记录，如果没有找到对应的位置，就后移，直到找到对应的位置。**)\*\*的方式。

## 时间复杂度 ##

在希尔排序中，因为增量递减的量，都没有一个具体的规则，希尔排序时间复杂度不太好评估。

借用**搜狗百科**的一段话。  
希尔排序的时间的时间复杂度为O(n平方)，希尔排序时间复杂度的下界是n\*log2n。希尔排序没有快速排序算法快 O(n(logn) ,因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。

## 稳定性 ##

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

# 后记 #

> 程序猿学社的GitHub，欢迎**Star：**  
> https://github.com/ITfqyd/cxyxs  
> 觉得有用,可以**点赞,关注,评论，留言**四连发。

[Link 1]: https://blog.csdn.net/qq_16855077/article/details/104228449
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3E1MnlrazBhYy5ia3QuY2xvdWRkbi5jb20vRmhTWDFPYnVCb01MNUpnMjJSdU5MMnItd19hNw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3E1MnlrazBhYy5ia3QuY2xvdWRkbi5jb20vRnVsRmNQcVhtWWZqTFdjYXJNYWVISmRiOGgzZQ?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL3E1MnlrazBhYy5ia3QuY2xvdWRkbi5jb20vRnRNLXFVRFZIcFVuRnpzaTItUEZmU19ZcXNURw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovL3E1MnlrazBhYy5ia3QuY2xvdWRkbi5jb20vRmtZR0szRlFWQTVCeklWYUxOTDFKeWJobVIxSg?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cDovL3E1MnlrazBhYy5ia3QuY2xvdWRkbi5jb20vRmhycTVvSG9lemxNQWRhaXdTTzVBVlBFS3dmQw?x-oss-process=image/format,png