希尔排序的Java代码实现

• 时间复杂度

  最好： O(n^1.3)
  最坏 ： O(n²)

• 原理图片
  

注意： 不用一定取奇数!!!

public class Test01 {
    public static void main(String[] args) {
        int[] nums = new int[]{9,-8,-10,6,1,8,-20,2};
        System.out.println("原始数据：" + Arrays.toString(nums));
        new Test01().ShellSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void ShellSort(int[] nums){
        //初始化步长
        int gap = nums.length;
        while(true){
            gap /= 2;
            //针对步长内的每个数字进行排序(直接插入排序)
            for(int i = 0; i < gap; i++){
                //直接插入排序
                for(int j = i + gap; j < nums.length; j = j + gap){
                    int index = j;
                    int number = nums[j];
                    while (index - gap >=0 && number < nums[index - gap]){
                        nums[index] = nums[index - gap];
                        index -= gap;
                    }
                    nums[index] = number;
                }
            }
            System.out.println("步长 = " + gap + "; 排序结果：" + Arrays.toString(nums));
            if(gap == 1){
                break;
            }
        }
    }
}

希尔完事，插入排序(直接插入排序、希尔排序)完事!!!