何为希尔排序

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

概述

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

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

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

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

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

这个结论更加显而易见，插入排序的工作量和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;    }

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