希尔排序就这么简单

paulli3 发布于2019-08-19 10:43 / 384人阅读

摘要：这时就用简单插入排序将数列直至已序从直观上看希尔排序就是把数列进行分组不停使用插入排序，直至从宏观上看起来有序，最后插入排序起来就容易了无须多次移位或交换。

一、希尔排序介绍

来源百度百科：

希尔排序(Shell"s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

从上面我们很容易看出来，它是插入排序的高级版

回顾一下插入排序：

将数据插入到已有序的数列中

排序前：将每个元素看成有序的数列

第一趟排序后：得到一个有序数列，其大小为2

第二趟排序后：得到一个有序数列，其大小为3

第三趟排序后：得到一个有序数列，其大小为4

........每一趟插入排序，都可以将一个无序值插入一个有序数列，直至全部值有序

如果给出的数组足够乱的话，那么插入排序所耗费的时间是O(n^2)

既然希尔排序是插入排序的高级版，那它做了哪些优化呢？？让我们来看看：

希尔排序在排序前：将一个序列分成了好几个序列

在第一趟排序时：将这几个序列做插入排序。排序后，部分较大的数字往后靠，部分较小的数字往前靠

在第二趟排序时：将这个序列又分了好几个序列做插入排序(但比第一次分的数要少,ps:如果第一次分5个，第二次可能就2个了)。排序后，部分较大的数字往后靠，部分较小的数字往前靠

................

在第n趟排序时：将这个序列又分了好几个序列(直到剩下一个序列)，从宏观上看，此序列就基本是有序的了。这时就用简单插入排序将数列直至已序

从直观上看希尔排序：

就是把数列进行分组(不停使用插入排序)，直至从宏观上看起来有序，最后插入排序起来就容易了(无须多次移位或交换)。

那么，上面那里说了将一个序列分成好几个序列，那么到底怎么分呢？比如有10个元素的序列，分成几个才合适？每次缩减又是多少呢？

从专业的角度上讲，将一个序列分成好几个序列，用一个数来表示：那个数称为增量。显然的是，增量是不断递减的(直到增量为1)

往往的：如果一个数列有10个元素，我们第一趟的增量是5，第二趟的增量是2，第三趟的增量是1。如果一个数列有18个严肃，我们第一趟的增量是9，第二趟的增量是4，第三趟的增量是2，第四趟的增量是1

很明显我们可以用一个序列来表示增量：{n/2,(n/2)/2...1}，每次增量都/2

二、希尔排序体验

现在我们有一个数组，该数组有6个元素

      int[] arrays = {2, 5, 1, 3, 4, 6};

排序前：

将该数组看成三个（arrays.length/2)数组，分别是:{2,3},{5,4},{1,6}

第一趟排序：

对三个数组分别进行插入排序，因此我们三个数组得到的结果为{2,3},{4,5},{1,6}

此时数组是这样子的：{2, 4, 1, 3, 5, 6}

第二趟排序：

增量减少了，上面增量是3，此时增量应该为1了，因此把{2, 4, 1, 3, 5, 6}看成一个数组(从宏观上是有序的了)，对其进行插入排序，直至有序

可能我举的例子不够好(没看到很好的效果)，我们来看看网上的图片，加深一下希尔排序的过程：

PS:图片来源网上(侵删)

三、希尔排序代码实现


    public static void shellSort(int[] arrays) {


        //增量每次都/2
        for (int step = arrays.length / 2; step > 0; step /= 2) {

            //从增量那组开始进行插入排序，直至完毕
            for (int i = step; i < arrays.length; i++) {

                int j = i;
                int temp = arrays[j];

                // j - step 就是代表与它同组隔壁的元素
                while (j - step >= 0 && arrays[j - step] > temp) {
                    arrays[j] = arrays[j - step];
                    j = j - step;
                }
                arrays[j] = temp;
            }
        }


    }

我们发现希尔排序代码其实非常简单(相比对堆排序)，理解起来也不难，就用增量来将数组进行分隔，直到增量为1。底层干的还是插入排序干的活～

四、最后

参考资料：

http://blog.csdn.net/jianfpeng241241/article/details/51707618

http://blog.csdn.net/robomaster/article/details/50953265

https://www.cnblogs.com/chengxiao/p/6104371.html

如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以关注微信公众号:Java3y

GPU云服务器云服务器希尔排序最简单的排序算法简单的c语言排序希尔

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76359.html

八大基础排序总结

摘要：不断执行这个操作代码实现快速排序用递归比较好写如果不太熟悉递归的同学可到递归就这么简单。前言大概花了一周的时间把八大基础排序过了一遍，这篇博文主要是用来回顾一下八大基础排序的要点和一些总结～回顾：冒泡排序就这么简单选择排序就这么简单插入排序就这么简单快速排序就这么简单归并排序就这么简单堆排序就这么简单希尔排序就这么简单基数排序就这么简单总的来说：快速排序是用...

maochunguang 2019-08-16 11:07 评论0 收藏0
JS中可能用得到的全部的排序算法

本篇有7k+字, 系统梳理了js中常见的12种排序算法。除了基本排序算法，文章还包含了希尔排序、堆排序、桶排序等较为复杂的排序实现，如果喜欢请点赞支持~谢谢. 原文: http://louiszhai.github.io/20... 导读排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道...

verano 2019-08-20 15:08 评论0 收藏0
基本算法学习(一)之希尔排序(JS)

摘要：动态定义间隔序列参考来源详细介绍了十种算法大家可以去学习下以后大概会尽量每天更新一个算法学习吧温故而知新参考书:严蔚敏-数据结构希尔排序(Shells Sort) 希尔排序又称缩小增量排序,归属于插入排序一类,简单来说,和我们的插入排序比,它更快. 奇妙的记忆点: 内排序(内存排序就够了) 不稳定(排序后原始顺序无法保证) 希尔排序重点在于分割. 基本思想: 将整个待排序记录序...

cooxer 2019-08-20 11:09 评论0 收藏0
数据结构与算法——希尔、归并、快速排序

摘要：今天再来看看另外三种时间复杂度都是的排序算法，分别是希尔排序归并排序和快速排序。三数取中法求将放到数组的末尾总结这三种排序算法的平均时间复杂度都是，归并排序和快速排序的应用更广泛。 1. 回顾前面说完了三种较为简单的排序算法，分别是冒泡排序，选择排序和插入排序，它们的平均情况时间复杂度都是 O(n2)，比较的高，适合小规模的数据排序，其中插入排序的效率稍高，所以更推荐使用插入排序。今...

hersion 2019-08-16 15:58 评论0 收藏0