1.希尔排序

希尔排序是插入排序的改进，不必再像插入排序一样一个一个比较再交换，它的精髓在于增量交换，因此又叫做缩小增量排序。常用初始增量为len/2，这样就把所有元素分为了若干组，每次通过比较、交换相差增量的元素，然后缩小增量，重复这个过程直至增量变为1，这样每一个元素都排好了位置。

希尔排序的时间复杂度为O(nlogn)，是首个时间复杂度冲破O(n^2)的算法。

下面是它的java代码实现

@Test
public void sort(){
    int []array = new int[100000];
    Random random = new Random();
    for (int i =0;i < 100000;i++){
        array[i]= random.nextInt(9000000);
    }
    //实现
    for (int d = array.length/2 ; d > 0 ; d/=2) {//初始增量d为len/2，每次缩小一半直至最后为1
        for (int i = d ;i<array.length;i++){//循环每一个分组
          for (int j = i-d;j>=0 && array[j+d]<array[j];j-=d){//同一组且相邻增量的元素比较大小并交换，此循环结束代表该组的大小排序完成
              swap(array,j,j+d);
          }
        }
    }
    log.info(Arrays.toString(array));
}

//交换元素
void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

经过测试，10w个元素的数组使用希尔排序耗时436ms

2.插入排序
看不懂希尔排序的话，不如先看看插入排序，插入排序顾名思义，把最小或最大的元素插入到合适的位置直至遍历所有元素即可。
也就是说插入排序要把第一个元素看作是有序的，从第二个元素开始和前一个元素比较大小，若符合条件则交换他们，重复这个过程直到不符合条件为止，
这样一来这个元素之前的都是有序的，之后的都是无序的。重复这个过程直到最后一个元素比较完，排序就结束了。
插入排序时间复杂度为O(n^2)
下面是代码实现

@Test
public void sort(){
    int []array = new int[100000];
    Random random = new Random();
    for (int i =0;i < 100000;i++){
        array[i]= random.nextInt(9000000);
    }
    //实现
    for (int i = 1;i<array.length;i++){
        for (int j = i-1;j>=0;j--){
            if (array[j+1]<array[j]){
                swap(array,j,j+1);
            }
        }
    }
    log.info(Arrays.toString(array));
}

经过测试，10w个元素的数组使用插入排序耗时10s175ms

是不是相差挺大的，当数据量小的时候两个算法差异还差不多，数据量大起来，耗费的时间只会越拉越大。