希尔排序

希尔排序是对直接插入排序的改进,其实质就是分组插入排序,该方法又称缩小增量排序。 该算法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的一系列元素组成)分别进行直接插入排序,然后依次缩减增量再进行排序,直到增量为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步长。

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券