首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >希尔排序

希尔排序

作者头像
卡尔曼和玻尔兹曼谁曼
发布2019-01-22 10:32:09
5010
发布2019-01-22 10:32:09
举报

希尔排序是对直接插入排序的改进,其实质就是分组插入排序,该方法又称缩小增量排序。 该算法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的一系列元素组成)分别进行直接插入排序,然后依次缩减增量再进行排序,直到增量为1(即对全体数据元素进行一次直接插入排序)。 希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。

希尔排序图示(来自百度图片,若侵权,请告知):

希尔排序
希尔排序

在实现希尔排序的时候,我们先看一眼直接插入排序的实现,然后在看希尔排序的实现,我们会发现,其实希尔排序就比直接插入排序多了一个基于步长的外层循环。 直接插入排序Java版:

public static void insertSort(int[] numbers) {
    for (int i = 1; i < numbers.length; i++) {
        int number = numbers[i];
        int j = i - 1;
        while (j >= 0 && numbers[j] > number) j--;
        for (int k = i; k > j + 1; k--)
            numbers[k] = numbers[k - 1];
        numbers[j + 1] = number;
    }
}

希尔排序Java版:

public static void shellSort(int[] numbers) {
    for (int gap = numbers.length / 2; gap > 0; gap /= 2) {
        for (int i = 1; i < numbers.length; i += gap) {
            int number = numbers[i];
            int j = i - gap;
            while (j >= 0 && numbers[j] > number) j -= gap;
            for (int k = i; k > j + gap; k -= gap)
                numbers[k] = numbers[k - gap];
            numbers[j + gap] = number;
        }
    }
}

可以看到,希尔排序就增加了一个外层的基于步长的循环,然后内部是直接插入排序,只不过循环的增量不是1,而是外层的那个gap步长。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年05月11日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档