何为希尔排序

这篇文章主要讲解了“何为希尔排序”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“何为希尔排序”吧！

概述

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

这个结论很明显，如果一个数组大部分元素都有序，那么数组中的元素自然不需要频繁地进行比较和交换。

• 在元素数量较少的情况下，插入排序的工作量较小

这个结论更加显而易见，插入排序的工作量和n的平方成正比，如果n比较小，那么排序的工作量自然要小得多

也就是说：如果我们对数据做一些 “预处理”，使得原始数组的大部分元素变得有序，那么我们再使用插入算法进行排序，那么排序的效率将会大大提高。希尔排序正事基于这种思路实现的。

举个栗子

这是我们现在拿到的原始数组：

第一轮，我们取总长度的一半，也就是4，作为跨度，这样两两一组，总共事4组：

接下来，我们让每组元素进行独立排序，排序方式用直接插入排序即可。由于每一组的元素数量很少，只有两个，所以插入排序的工作量很少。每组排序完成后的数组如下：

这样一来，仅仅经过几次简单的交换，数组整体的有序程度得到了显著提高，使得后续再进行直接插入排序的工作量大大减少。这种做法，可以理解为对原始数组的“粗略调整”。 但是这样还不算完，我们可以进一步缩小分组跨度，重复上述工作。把跨度缩小为原先的一半，也就是跨度为2，重新对元素进行分组，一共两组：

接下来，我们继续让每组元素进行独立排序，排序方式用直接插入排序即可。每组排序完成后的数组如下：

最后，我们把分组跨度进一步减小，让跨度为1，也就等同于做直接插入排序。经过之前的一系列粗略调整，直接插入排序的工作量减少了很多，排序结果如下：

让我们重新梳理一下分组排序的整个过程：

代码实现：

    public static int[] sort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int step = arr.length / 2;
        for (; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                int temp = arr[i];
                int j = i;
                for (; j >= step && temp < arr[j - step]; j -= step) {
                    //符合条件往后移
                    arr[j] = arr[j - step];
                }
                arr[j] = temp;
            }
        }
        return arr;
    }

感谢各位的阅读，以上就是“何为希尔排序”的内容了，经过本文的学习后，相信大家对何为希尔排序这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！