[数据结构与算法]希尔排序(Shell sort)

原理

通过相距一定间隔的元素来工作，各轮对比所用的距离随着算法的进行而减小，走到只比较相邻元素的最后一轮排序位置，所以，它也叫作缩减增量排序。

从某一程度来看，它是插入排序的升级版

3 2 5 9 7 4 1 8 —— 3 2 1 8 7 4 5 9 —— 1 2 3 4 5 8 7 9 —— 1 2 3 4 5 7 8 9

默认的增量为length/2，例中数长度为8，则默认增量为4，那么第一个元素将与第五（1+4）个元素对比，其余元素以此类推。

希尔排序并不要求增量的大小，除以2是惯例做法

以升序为例，如果左侧的同一组数据较大，则换位

第一轮对比结束后，接下来将增量在原来的基础上除以2，所以新增量是4/2=2，即使第一个与第三个做对比。（代码实现时，使用插入排序）

最后一轮，增量为1，即比较相邻的元素，全部参与排列（1/2 = 0，所以为最后一轮）

对于局部有序的数组，插入排序效率很高，即使全部排序也非常快

特殊情况

根据增量确定对比关系后，各组对应关系的数量不统一怎么办？

通常是数组右侧的若干个元素 3 2 5 9 7 4 1 8 6

这种情况在排序时，会先暂时跳过增量值对应数量的元素，然后向右对比，并每次对比 当前下标-增量值 对应的下标的元素

实现步骤

import java.util.Arrays;
import java.util.Random;

public class ShellSort {
    public static void main(String[] args) {
        Random rd = new Random();
        //生成数组
        int[] arr = new int[rd.nextInt(100)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rd.nextInt(500);
        }
        System.out.println(Arrays.toString(arr));
        int tem;//存储临时数据
        int swapCount = 0;//换位次数
        int compareCount = 0;//对比次数
        long start = System.currentTimeMillis();//开始时间

        for (int i = arr.length / 2; i > 0 ; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                //随着循环轮数的增加，最右边的数要对比的数越来越多，需要新的循环处理
                for (int p = j - i; p >= 0; p -= i) {
                    //判断需要对比的同组元素并执行换位
                    //换位为插入排序
                    if (arr[p + i] < arr[p]) {
                        tem = arr[p + i];
                        arr[p + i] = arr[p];
                        arr[p] = tem;
                        swapCount++;
                    }else {
                        break;
                    }
                    compareCount++;
                }
            }
        }
        long end = System.currentTimeMillis();//结束时间
        System.out.println(swapCount);
        System.out.println(compareCount);
        System.out.println(end - start);
        System.out.println(Arrays.toString(arr));
    }
}