编辑代码

import java.util.Arrays;

class Main {
	public static void main(String[] args) {
        int[] arr = new int[]{8,9,1,7,2,3,5,4,6,0};     
        // shellSort(arr);
        //shellSortUpgrade(arr);    
        moved();    
	}
    //使用逐步推导的方式来编写希尔排序
    public static void shellSort(int[] arr){
        //第一轮希尔排序
        //因为第一轮排序是将10个数据分成了5组
        int temp = 0;
        for(int i = 5;i < arr.length; i++){
            //遍历各组中所有的元素(共有5组，每组有2个元素))，步长5
            for(int j = i - 5; j >= 0; j -= 5){
                //如果当前元素大于加上步长的那个元素，说明交换
                if(arr[j] > arr[j + 5]){
                    temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }
        System.out.println("希尔排序第一轮 = "+Arrays.toString(arr));

        //第二轮希尔排序
        //因为第二轮排序是将10个数据分成了5/2 = 2组
        for(int i = 2;i < arr.length; i++){
            //遍历各组中所有的元素(共有5组，每组有2个元素))，步长5
            for(int j = i - 2; j >= 0; j -= 2){
                //如果当前元素大于加上步长的那个元素，说明交换
                if(arr[j] > arr[j + 2]){
                    temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }

        System.out.println("希尔排序第二轮 = "+Arrays.toString(arr));

        //第三轮希尔排序
        //因为第三轮排序是将2个数据分成了2/2 = 1组
        for(int i = 1;i < arr.length; i++){
            //遍历各组中所有的元素(共有5组，每组有2个元素))，步长5
            for(int j = i - 1; j >= 0; j -= 1){
                //如果当前元素大于加上步长的那个元素，说明交换
                if(arr[j] > arr[j + 1]){
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        System.out.println("希尔排序第三轮 = "+Arrays.toString(arr));
    }

    //使用循环来优化
    public static void shellSortUpgrade(int[] arr){
        int len = arr.length;
        int temp = 0;
        do{
            len /= 2;
            for(int i = len; i < arr.length; i++){
                for(int j = i - len; j >= 0; j -= len){
                    if(arr[j] > arr[j + len]){
                        temp = arr[j];
                        arr[j] = arr[j + len];
                        arr[j + len] = temp;
                    }
                }
            }
        }while(len != 1);
        System.out.println("希尔排序的最终结果 =" + Arrays.toString(arr));
    }

    //对交换式的希尔排序进行优化 -> 移动位
    public static void shellSortMoved(int[] arr){
        for(int len = arr.length / 2; len > 0; len /= 2){
            //从第len个元素开始逐个对其所在的组进行直接插入排序
            for(int i = len;i < arr.length; i++){
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j - len]){
                    while(j - len >= 0 && temp < arr[j = len]){
                        //移动
                        arr[j] = arr[j - len];
                        j -= len;
                    }
                    //当退出while循环后，就给temp找到了插入的位置
                    arr[j] = temp;
                }
            }
        }
        System.out.println("希尔排序的最终结果 =" + Arrays.toString(arr));
    }
}