希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。优先的排序算法首要条件就是速度，在简单排序出现后的很多一段时间内，人们发明了各种各样的算法，但是最终发现算法的时间复杂度都是O(N²)，似乎没法超越了。此时，计算机学术界充斥着"排序算法不可能突破O(N²)"的声音。终于有一天，一位科学家发布超越了O(N²)的新排序算法(后来为了纪念这个里程碑，用Shell来命名了该算法)。

(2).插入排序的问题

假设一个很小的数据项在很靠近右端的位置上，这里本来应该是较大的数据项的位置。把这个小数据项移动到左边的正确位置，所有的中间数据项都必须向右移动一位。如果每个步骤对数据项都进行N次复制，平均下来是移动N/2，N个元素就是 N*N/2 = N²/2。通常认为插入排序的效率是O(N²)。

(3).希尔排序的做法

比如上面的数字, 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15。

先让间隔为5进行排序. (81, 35, 41), (94, 17, 75), (11, 95, 15), (96, 28), (12, 58)

排序后的新序列, 一定可以让数字离正确位置更近一步。

再让间隔位3进行排序. (35, 28, 75, 58, 95), (17, 12, 15, 81), (11, 41, 96, 94)

排序后的新序列, 一定可以让数字离自己的正确位置又近了一步。

最后，让间隔为1，也就是正确的插入排序。这个时候数字都离自己的正确位置更近，那么需要复制的次数就会减少很多。

(4).选择合适的增量

在希尔排序的原稿中建议的初始间距是N / 2，简单的把每一回排序分成两半。也就是说，对于N = 100的数组，增量间隔序列为： 50, 25, 12, 6, 3, 1。这个方法的好处是不需要在开始排序前为找合适的增量而进行任何的计算

2.希尔排序的实现


    //希尔排序
    ArrayList.prototype.shellSort = function () {
        //1.获取数组长度
        var length = this.array.length
        //2.初始化的增量
        var gap = Math.floor(length / 2)
        //3.while循环（gap不断的减小）
        while (gap >= 1) {
            //4.以gap作为间隔，进行分组，对分组进行插入排序
            for (var i = 0; i < length; i++) {
                var temp = this.array[i]
                var j = i
                while (this.array[j - gap] > temp && j > gap - 1) {
                    this.array[j] = this.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/786859

数据结构与算法 — 希尔排序 和 快速排序_希尔排序和快速排序

一. 希尔排序

1.希尔排序的介绍

(1).希尔排序的历史背景

(2).插入排序的问题

(3).希尔排序的做法

(4).选择合适的增量

2.希尔排序的实现

数据结构与算法 — 希尔排序和快速排序_希尔排序和快速排序