希尔排序的几种实现方式

在学习希尔排序时，可以通过使用交换式实现，也可以通过移位式实现

以下所有时间都是按照对一个随机生成的大小为80000的数组进行排序过程所用时间

第一种，交换式实现，这种方式在最后一轮，也就是分成一组，步长为1时，完成了一次交换式的插入排序，总共花费了11521ms，但是如果只运行最后一组，也能实现排序，花费5121ms（和交换法实现插入排序差不多）

//交换法实现希尔排序  11521ms
public static void shellSort1(int[] arr) {
        int temp = 0;
        for (int gap=arr.length/2;gap>0;gap/=2){
            for (int i=gap;i<arr.length;i++){
                for (int j=i-gap;j>=0;j-=gap){
                    if (arr[j]>arr[j+gap]){
                        temp=arr[j];
                        arr[j]=arr[j+gap];
                        arr[j+gap]=temp;
                    }
                }
            }
        }
}

//交换法实现插入排序  5121ms
public static void insertSort(int[] arr){
    int temp=0;
        for (int i=1;i<arr.length;i++){
            for (int j=i-1;j>=0;j--){
                if (arr[j]>arr[j+1]){
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
}

第二种，移位式实现，这种方式在最后一轮也完成了一组完整的插入排序，耗时17ms，原先单独的一组移位式的插入排序时间是741ms

//移位式实现希尔排序  17ms
public static void shellSort2(int[] arr){
        int insertVal=arr[0];
        int insertIndex=0;
        for (int gap=arr.length/2;gap>=1;gap/=2){
            for (int i=gap;i<arr.length;i++){
                insertVal=arr[i];
                insertIndex=i-gap;
                while (insertIndex>=0 && insertVal<arr[insertIndex]){
                    arr[insertIndex+gap]=arr[insertIndex];
                    insertIndex-=gap;
                }
                if ((insertIndex+gap)!=i){
                    arr[insertIndex+gap]=insertVal;
                }
            }
        }
}

//移位式实现插入排序  741ms
 public static void insertSort(int[] arr){
        int insertVal=arr[1];
        int insertIndex=1;

        for (int i=1;i<arr.length;i++){
            insertIndex=i-1;
            insertVal=arr[i];
            while (insertIndex>=0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            if (!(insertIndex+1==i)){
                arr[insertIndex+1]=insertVal;
            }
        }
}