是插入排序经过改进之后的高效版本，也称缩小增量排序。
1959 年提出，是突破时间复杂度 O(n2)的第一批算法之一。
缩小增量排序的最优增量选择是一个数学难题，一般采用希尔建议的增量，具体如下。
思路与步骤：
-
首次选择的增量(即步长，下同)step= 数组长度 / 2 取整；缩小增量step，每次减半，直到为 1 结束缩小；逐渐缩小的增量组成一个序列：[n/2, n/2/2, … 1]
-
对数组进行 序列里增量的个数 趟排序
-
每趟排序，把增量作为间隔，将数组分割成若干子数组，分别对各子数组进行插入排序
-
当增量等于 1 时，排序整个数组后，排序完成
代码：
package constxiong.interview.algorithm;/** *希尔排序 * @author ConstXiong * @date 2020-04-11 11:58:58 */public class ShellSort {public static void main(String[] args) {int [] array = {33, 22, 1, 4, 25, 88, 71, 4};shellSort(array);}/** * 希尔排序 * @param array */private static void shellSort(int[] array) {print(array);int length = array.length;int step = length / 2; //步长，默认取数组长度一半int temp; while (step > 0) {for (int i = step; i <length; i++) { //从步长值为下标，开始遍历temp = array[i]; //当前值int preIndex = i - step; //步长间隔上一个值的下标//在步长间隔的的数组中，找到需要插入的位置，挪动右边的数while (preIndex >= 0 && array[preIndex] > temp) { array[preIndex + step] = array[preIndex];preIndex -= step;}//把当前值插入到在步长间隔的的数组中找到的位置array[preIndex + step] = temp;}step /= 2;print(array);}}/** * 打印数组 * @param array */private static void print(int[] array) {for(int i : array) {System.out.print(i + " ");}System.out.println();}}打印：
33 22 1 4 25 88 71 4 25 22 1 4 33 88 71 4 1 4 25 4 33 22 71 88 1 4 4 22 25 33 71 88 特征：
- 空间复杂度为 O(1)，是原地排序算法
- 最好、最坏、平均情况时间复杂度，都是 O(nlog2 n)
- 非稳定排序。因为进行了增量间隔分组排序，可能导致相等的值先后顺序变换
