希尔排序【Shellsort】

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。——维基百科

希尔排序是基于插入排序的以下两点性质而提出改进方法的: – 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 – 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

算法实现

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。

步长序列

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为插入排序,这就保证了数据一定会被排序。 推荐步长: 3*n+1

算法分析

1.增量序列的选择 Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征: – 最后一个增量必须为1; – 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

2.Shell排序的时间性能优于直接插入排序 – 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 – 当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 – 在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。

3.稳定性 希尔排序是不稳定的。

排序算法的稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

public class Shell
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        int h = 1;
        while(h < N/3) h = 3*h +1;
        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/3;
        }
    }
    private static boolean less(Comparable v, Comparable w)
    {
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a, int i, int j)
    {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/shellsort/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python计算信息熵

信息熵可以用来判定指定信源发出的信息的不确定性,信息越是杂乱无章毫无规律,信息熵就越大。如果某信源总是发出完全一样的信息,那么熵为0,也就是说信息是完全可以确定...

5064
来自专栏数据结构与算法

10:大整数加法

10:大整数加法 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 求两个不超过200位的非负整数的和。 输入有两行,每...

47812
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版5.6节C风格数据结构内存布局之复合类型构成的结构体

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

1081
来自专栏calmound

uva Andy's First Dictionary

题目很简单,数组开大就好,5000但加上重复就不够了10000都小,sort排序前闭合后开,对二维字符窜排序用结构体,所以只有一组的时候只是本身但是不会出现RE...

3474
来自专栏机器学习从入门到成神

数据库中关系代数中的关系运算

这个概念的描述的非常抽象,刚开始学习的同学完全不知所云。这里通过一个实例来说明除法运算的求解过程:

1.6K2
来自专栏小文博客

小文’s blog — 方程整数解 –《蓝桥杯代码笔记1》

1102
来自专栏林德熙的博客

win10 uwp 初始屏幕

对于本地 127.0.0.1 就是一个内部IP,之外,还有10.0.0.0/24 ,172.16.0.0/16 , 192.168.0.0/16 , 169.2...

912
来自专栏林德熙的博客

win10 uwp 判断本地ip

对于本地 127.0.0.1 就是一个内部IP,之外,还有10.0.0.0/24 ,172.16.0.0/16 , 192.168.0.0/16 , 169.2...

1201
来自专栏数据科学学习手札

(数据科学学习手札07)R在数据框操作上方法的总结(初级篇)

上篇我们了解了Python中pandas内封装的关于数据框的常用操作方法,而作为专为数据科学而生的一门语言,R在数据框的操作上则更为丰富精彩,本篇就R处理数据框...

3598
来自专栏机器学习从入门到成神

数据库闭包和候选码求解方法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1K1

扫码关注云+社区

领取腾讯云代金券