被排序算法吊打之—希尔排序

1. 希尔排序思想

希尔排序(Shell Sort)是插入排序的一种，是直接插入排序算法的一种更高效的改进版本。具体高效在何处呢？

前面俺讲插入排序的时候，我们会发现一个很费劲的事儿，如果已排序的分组元素为{2,5,6,7,8,9}，未排序的分组 元素为{1}。

我们需要拿着1从后往前，依次和2,5,6,7,8,9进行交换位置，才能完成真正的插入，每次交换只能和相邻的元素交换位置，这样比实在是效率低下。但是，在插入排序时俺说了折半插入，这算是一种优化，但是如果我要是将1插入到2,5,1,7,8,9当中，是不是就不行啦？

那我可不可以这样做呢？

把1放到更前面的位置，比如一次交换就能把1插到6和7之间，这样一次交换1就向前走了3个位置，可以减少交换的次数，然后再通过一次交换，直接结束排序。这样的需求如何实现呢？接下来我们来看看希尔排序的原理。

2. 希尔排序详解

排序原理：

1. 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；

2. 对分好组的每一组数据完成插入排序；

3. 减小增长量，最小减为1，重复第二步操作。

---

增长量ans：我们这里采用以下规则

【第一趟排序】

初始增量为ans = length/2 = 4，即将整个数组划分为4个子组，分别为4,6，8,2，9,6，7,1

将每个子组独立的看为一个要排序的数组，然后分别进行直接排序。

可以看到，每个子序列现在已经有序了。但是将每个子序列回归放到整个数组中，发现整个数组还是乱序的。我们接着进行第二趟排序。

【第二趟排序】

二次增量为ans = 4/2 = 2，即将整个数组划分为4个子组，分别为4,6,6,9，2,1,8,7

然后在分别对两个子组进行插入排序

【第三趟排序】

第三次增量为ans = 2/2 = 1，即将每个元素看成一组，子序列合并为一组，4,1,6,2,6,7,9,8。

其实，这就是相当于直接插入排序。但是，经过第一趟、第二趟的处理之后，此时第三趟要排序的数组对比于原数组，我们发现它其实是被粗略调整过了，数组在一定程度上变得相对有序了。

此时，仅仅需要对以上数列简单微调，无需大量移动操作即可完成整个数组的排序。

3. 代码实现

public static void shellSort(Integer[] arr) {
        //根据数组长度，确定增长量ans
        int ans = 1;
        while (ans < arr.length/2) {
            ans = 2 * ans + 1;
        }
        while (ans >= 1) {
            //找到待插入的元素
            for (int i = ans; i < arr.length; i++) {
                //待插入的元素插入到分组的有序序列中
                for (int j = i; j >= ans; j-=ans) {
                    //待插入的元素时arr[j],比较arr[j-ans]
                    if(arr[j] < arr[j-ans]) {
                        int temp = arr[j];
                        arr[j] = arr[j-ans];
                        arr[j-ans] = temp;
                    }else {
                        //待插入元素在分组中已有序
                        break;
                    }
                }
            }
            //减小ans的值
            ans = ans / 2;
        }
    }

4. 复杂度分析

希尔排序，利用分组粗调的方式减少了直接插入排序的工作量，使得算法的平均时间复杂度低于0(n^2)。

【时间复杂度】O(nlogn)

【空间复杂度】O(1)

5. 希尔排序与插入排序比较

我们可以使用事后分析法对希尔排序和插入排序做性能比较。

测试从100000 ~ 1的逆向数据数组，我们可以根据执行时间来完成测试。

【执行时间】

• 希尔排序：29ms

• 直接插入排序：76826ms

• 折半插入排序：13075ms

可以看出，希尔排序的效率相比其他两种效率很高。这就是得益于每趟对数组进行的粗略调整。