前言

之所以把希尔排序作为排序系列的第3.5篇，是因为希尔排序可以称得上是 插入排序Plus ，它在插入排序的基础上继续升级，突破了时间复杂度O(n2)的壁障

手撕算法 - 排序系列

源码

希尔排序

思想

希尔排序中，有一个叫做增量的概念，在排序过程中需要按照增量分组 说白了，就是在一个数组中跳着选数组元素，归为一组，再将每个组进行直接插入排序 在所有组的直接插入排序完成后，将增量按照一定的规则缩小，再将上述操作进行一遍，直到增量最终小于1

例

假如传入了一个大小为10的随机数组[7,3,4,1,8,9,2,0,6,5]

让增量初始化为数组长度10，incr = 10 排序开始，我们假定增量缩小的规则为每次让增量折半，即incr/=2，此时incr = 5 我们将传入的一维数组看作n行5列的二维数组： [7,3,4,1,8] [9,2,0,6,5] 此时，我们将每一列归为一组，按组分为： [7,9] [3,2] [4,0] [1,6] [8,5] 再将这些组中所有出现逆序的组进行插入排序 一趟希尔排序完毕，将增量incr/=2，此时incr = 2 重复以上操作直到incr<1

时间复杂度

希尔排序的时间复杂度取决于传入数组和增量策略的设置，一般来说，其时间复杂度范围在O(n*logn)~O(n2），平均时间复杂度为O(n1.5)

实现

public static void sort(int[] arr) {
          
   
        int len = arr.length;
        int incr = len;
        while(incr>1){
          
   
            // 每趟希尔排序，都让增量的值折半
            incr/=2;
            for(int i=incr;i<len;++i){
          
   
                if(arr[i]<arr[i-incr]){
          
   
                	// 分组插入排序             	
            		// 当遍历时遇到相对有序，直接进行下一趟排序
                    for(int j=i;j>=incr && arr[j]<arr[j-incr];j-=incr){
          
   
                        Swaper.exec(arr,j,j-incr);
                    }
                }
            }
        }
    }

测试

排序测试：

由于希尔排序是时间性能突破了O(n2)的优秀排序算法，这次的测试用例数组直接上百万~

百万级数组耗时测试：

int n = 1_000_000;
    int[] tmp = Tester.randomArr(n);
    int[] arr = tmp.clone();
    System.out.println("对有" + n + "个元素的随机数组进行排序：");
    long start = System.currentTimeMillis();
    sort(arr);
    long end = System.currentTimeMillis();
    System.out.println("希尔排序结束，耗时" + (end - start) + "ms");

结果：

是不是比之前那些O(n2)排序要快得多了~