排序算法-希尔排序

对插入排序的改进

思路：将数组数据分组，将第一个数与中间数分为一组，两两比较交换，在增加每组数量，四四一组比较交换

推导代码：

package sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
    }

    public static void shellSort(int[] arr){
        int temp = 0;
        //第一轮
        for (int i = 5; i < arr.length; i++) {
            //遍历所有元素，每组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));
        //第二轮
        for (int i = 2; i < arr.length; i++) {
            //遍历所有元素，每组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("第2轮"+ Arrays.toString(arr));
        //第3轮
        for (int i = 1; i < arr.length; i++) {
            //遍历所有元素，每组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("第3轮"+ Arrays.toString(arr));
    }
}

具体代码

package sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
    }

    public static void shellSort(int[] arr){
        int temp = 0;
        for (int gap = arr.length/2;gap > 0;gap /= 2){
            //第一轮
            for (int i = gap; i < arr.length; i++) {
                //遍历所有元素，每组2元素，步长为5
                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;
                    }
                }
            }
            System.out.println( Arrays.toString(arr));

        }


    }
}

此时运行时间大于插入排序，优化

public static void shellSort2(int[] arr){
    for (int gap = arr.length/2;gap > 0;gap /= 2) {
        //进行插入排序
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            if (arr[j] < arr[j - gap]){
                while (j - gap >= 0 && temp < arr[j - gap]){
                    //移动
                    arr[j] = arr[j -gap];
                    j -= gap;
                }
                //当退出循环，就给temp找到插入位置
                arr[j] =temp;
            }
        }
    }
    System.out.println( Arrays.toString(arr));
}