希尔排序（Shell’s Sort）

1. 什么是希尔排序

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

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

插入排序在对简直曾经排好序的数据操作时，效率高，即能够达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据挪动一位；
希尔排序的根本思维是：先将整个待排序的记录序列宰割成为若干子序列别离进行间接插入排序，待整个序列中的记录 ” 根本有序 ” 时，再对整体记录进行顺次间接插入排序。

2. 算法步骤

抉择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，依据对应的增量 ti，将待排序列宰割成若干长度为 m 的子序列，别离对各子表进行间接插入排序。仅增量因子为 1 时，整个序列作为一个表来解决，表长度即为整个序列的长度。

3. 动图演示

4. 代码实现

public static void main(String[] args) {
        // 初始化数组
        int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};
        // 增量 gap，并逐渐的放大增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 从第 gap 个元素，一一对其所在的组进行间接插入排序
            for (int i = gap; i < arr.length; i++) {
                // 插入排序算法
                int temp = arr[i];
                int j = i;
                while(j > 0 && temp < arr[j - gap]){arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

5. 输入后果

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]