搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 地中海程序员 > 希尔排序算法解析

希尔排序算法解析

地中海程序员 2020-07-01
点击上方“蓝字”关注我们吧!
希尔排序算法解析
希尔排序算法定义
希尔排序算法解析

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

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止(摘自百度百科)。

简单点理解:就是先将要排序的数据分组,然后对每组数据做插入排序。


希尔排序算法解析
希尔排序代码
希尔排序算法解析

public static void desc(int nums[]) {

    //确定增量

    int h = nums.length;

    while (h >= 1) {

        h = h / 2;

        for (int i = h; i < nums.length; i ++) {

            for (int j = i; j >= h; j -= h) {

                if (nums[j] > nums[j - h]) {

                    int temp = nums[j];

                    nums[j] = nums[j - h];

                    nums[j - h] = temp;

                } else {

                    break;

                }

            }

        }

    }

}


希尔排序算法解析


 希尔排序代码图

希尔排序算法解析



排序详细过程
希尔排序算法解析

原数组:

[2, 4, 5, 1, 3, 6, 7, 9, 8, 0]

第一次排序,h=5,因此第一组数据为下标为0和5的数据。即2和6一组,做插入排序,6和2交换位置,同理,7和4,9和5,8和1也交换位置。

[6, 7, 9, 8, 3, 2, 4, 5, 1, 0]

第二次排序,h=2

[9, 8, 6, 7, 4, 5, 3, 2, 1, 0]

第三次排序h=1

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]


希尔排序算法解析




 排序过程图

希尔排序算法解析


希尔排序时间复杂度
希尔排序算法解析

希尔排序的时间的时间复杂度为O(n^(3/2)),希尔排序时间复杂度的下界是n*log2n,

Shell算法的性能与所选取的分组长度序列有很大关系。只对特定的待排序记录序列,可以准确地估算关键词的比较次数和对象移动次数。想要弄清关键词比较次数和记录移动次数与增量选择之间的关系,并给出完整的数学分析,今仍然是数学难题.(摘自百度百科),


希尔排序算法解析



希尔排序和插入排序性能比较
希尔排序算法解析

准备了10万个数据,顺序排列,现用插入排序和希尔排序分别将它变成倒序的。

int nums[] = new int[100000];

for (int i = 0; i < 100000; i++) {

    nums[i]=i;

}

最终得出时间:

插入排序时间:2719毫秒

希尔排序时间:5毫秒

可以看到在10万条数据排序的时候,希尔排序的效率远远高于插入排序。


希尔排序算法解析
结语
希尔排序算法解析

感谢各位的阅读,如有问题,欢迎大家留言反馈,我会在第一时间修正。

如果觉得文章还可以的话,不妨点个关注吧!!!








版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《希尔排序算法解析》的版权归原作者「地中海程序员」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注地中海程序员微信公众号

地中海程序员微信公众号:gh_ddbf9ae172ff

地中海程序员

手机扫描上方二维码即可关注地中海程序员微信公众号

地中海程序员最新文章

精品公众号随机推荐