希尔排序

x33g5p2x  于2021-12-06 转载在 其他  
字(2.4k)|赞(0)|评价(0)|浏览(218)

动画排序过程

执行流程

希尔排序是插入排序的改进版本,弥补了插入排序在某些情况下的缺点。
例如,当长度为100的数组,前面有序区域的数组长度为80,此时我们用第81个数去跟前面有序区域的所有元素比较大小,但恰巧第81个数又是这100个数里最小的,它本应该在索引为1的位置,如图所示

本例中第81个数据的值为1,那么前面有序区域里的80个元素都要往后移动一个位置,这种情况就非常影响排序性能。

因此,我们就要想办法尽可能早点让小的值靠前,让大的值靠后,这样就能避免上述情况了,这就是希尔排序要解决的问题。
希尔排序也叫做缩小增量排序,它通过先设置一个增量n(增量的求法是自己定义的,你的希尔排序的时间复杂度跟你自定义的增量规则有关,这里我们定义一个简单的增量规则n=n/2),大小为数组长度的一半,将间隔为n的元素视作一个组,然后对每个组内部的元素进行从小到大进行插入排序;然后再将增量n缩小一半,再次进行分组插入排序,直到增量n为1,因为增量为1的时候,所有的元素都为同一个组了

为了方便大家理解,我用一个例子来展示一个完整的希尔排序过程,首先数据的初始状态如图所示,这里为了更好地体现希尔排序的优点,我特地把值较大的元素放到了靠左的位置,把值较小的元素放到了靠右的位置

该数组长度为8,因此我们设置初始的增量为 8 / 2 = 4,那么该数组的分组情况如下图所示:

图中颜色相同的元素为一组,每组内的各个元素间隔都为4,现在对每个组内进行从小到大排序,排序结果如下图所示:

此时我们将增量缩小一半,即 4 / 2 = 2,同样的,现在将所有元素重新组合,把所有间隔为2的元素视作一组,分组结果如下图所示:

图中颜色相同的元素为一组,每组内的各个元素间隔都为2,现在对每个组内进行从小到大排序,排序结果如下图所示:

我们继续将增量缩小一半,即 2 / 2 = 1,同样的,现在将所有元素重新组合,把所有间隔为1的元素视作一组,此时所有的元素都为同一组了,就相当于对所有的数据进行普通的插入排序,我们可以看到,对比最开始的数据,总得来说,小的值都比较靠左了,大的值也都比较靠右了,这样排序起来效率就很高了。结果如下图所示:

接下来用一个动图,演示一下完整的希尔排序全过程

代码实现

根据上述流程的讲解相信大家都应该有思路了,接下来演示我写希尔排序的步骤
1、首先写出插入排序算法

public static void sort1(int[] arr) {
        for (int begin=1; begin<arr.length; begin++) {
            int cur = begin;
            int value = arr[cur]; // 定义一个临时值备份当前值
            while (cur-1>=0 && value<arr[cur-1]) {
                arr[cur] = arr[cur-1]; // 直接让前面的值覆盖后面的值,相当于直接移动,不存在交换
                cur--;
            }
            arr[cur] = value; // 最后把备份的值插入正确的位置
        }
    }

这段代码是「插入排序」我这篇文章中插入排序-优化01的代码,我们在这个段代码的基础上简单修改即可
2、首先加个for循环,step作为增量, 来表示根据增量不同,进行不同轮的排序,每一轮我们都使用插入排序对序列排序

for (int step=arr.length/2; step>0; step/=2){
            
}

3、将第一步中插入排序的代码直接放到循环中

for (int step=arr.length/2; step>0; step/=2){
    for (int begin=1; begin<arr.length; begin++) {
        int cur = begin;
        int value = arr[cur]; // 定义一个临时值备份当前值
        while (cur-1>=0 && value<arr[cur-1]) {
            arr[cur] = arr[cur-1]; // 直接让前面的值覆盖后面的值,相当于直接移动,不存在交换
            cur--;
        }
        arr[cur] = value; // 最后把备份的值插入正确的位置
    }
}

这段代码目前是不能运行的,接下来我们稍作修改

  1. 首先第二层for循环的初始值begin就不能为1了,应该为step
  2. 然后while循环里的条件要变一下,应该写成while (cur-step>=0 && value<arr[cur-step])
  3. while代码段里,改成arr[cur] = arr[cur-step]; cur-=step;

4、修改完成后的代码

//希尔排序
public static void sort(int[] arr) {
    for (int step=arr.length/2; step>0; step/=2){
        for (int begin=step; begin<arr.length; begin++) {
            int cur = begin;
            int value = arr[cur]; // 定义一个临时值备份当前值
            while (cur-step>=0 && value<arr[cur-step]) {
                arr[cur] = arr[cur-step]; // 直接让前面的值覆盖后面的值,相当于直接移动,不存在交换
                cur-=step;
            }
            arr[cur] = value; // 最后把备份的值插入正确的位置
        }
    }
}

总结

上述情况中,希尔排序最坏情况下的时间复杂度为O(n²)。其实希尔排序的时间复杂度跟增量也有关系,我们上面是通过数组长度一直取一半获取的增量,其实还有一些别的增量规则,可以使得希尔排序的效率更高,例如Hibbard增量序列Sedgewick增量序列,本文就不对这两种增量做过多的讲解了,大家可以去网上搜索一下。

参考优秀文章链接:https://blog.csdn.net/l_ppp/article/details/108855298

相关文章

微信公众号

最新文章

更多