希尔排序--学习

希尔排序

思路

1、选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组。

2、对每一个分好组的数据完成排序

3、减少增长量，最小减为1，重复第二步操作。

原始数据

第一次排序

我们选择增长量h为5 （也就是数组的长度/2）

整个数组被分为5组。

每一组进行比较交换

第二次排序

我们选择增长量为第一次的一半,h = 5/2 = 2

整个数组被分为2组

每一组进行比较交换

第三次排序

我们选择增长量为第一次的一半,h = 2/2 = 1

整个数组被分为1组

进行比较交换,这次排序后就得到了结果

第一次排序代码

public class ShellSort {
    public static void main(String[] args) {
        int[] value = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        new ShellSort().sort(value);
        for (int item : value) {
            System.out.print(item + ",");
        }
    }

    public void sort(int[] value){
        int temp = 0;
        for (int i = 5; i < value.length; i++) {
            for (int j = i - 5; j >= 0; j -= 5) {
                if (value[j] > value[j + 5]) {
                    temp = value[j];
                    value[j] = value[j + 5];
                    value[j + 5] = temp;
                }
            }
        }
    }
}

运行结果：4,1,2,3,5,9,8,6,5,7,

第二次排序代码

public class ShellSort {
    public static void main(String[] args) {
        int[] value = {4,1,2,3,5,9,8,6,5,7};
        new ShellSort().sort(value);
        for (int item : value) {
            System.out.print(item + ",");
        }
    }

    public void sort(int[] value){
        int temp = 0;
        for (int i = 2; i < value.length; i++) {
            for (int j = i - 2; j >= 0; j -= 2) {
                if (value[j] > value[j + 2]) {
                    temp = value[j];
                    value[j] = value[j + 2];
                    value[j + 2] = temp;
                }
            }
        }
    }
}

运行结果：2,1,4,3,5,6,5,7,8,9,

第三次排序代码

public class ShellSort {
    public static void main(String[] args) {
        int[] value = {2,1,4,3,5,6,5,7,8,9};
        new ShellSort().sort(value);
        for (int item : value) {
            System.out.print(item + ",");
        }
    }

    public void sort(int[] value){
        int temp = 0;
        for (int i = 1; i < value.length; i++) {
            for (int j = i - 1; j >= 0; j -= 1) {
                if (value[j] > value[j + 1]) {
                    temp = value[j];
                    value[j] = value[j + 1];
                    value[j + 1] = temp;
                }
            }
        }
    }
}

运行结果：1,2,3,4,5,5,6,7,8,9,

最终代码

我们用外层循环控制增长量h即可

public class ShellSort {
    public static void main(String[] args) {
        int[] value = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        new ShellSort().sort(value);
        for (int item : value) {
            System.out.print(item + ",");
        }
    }

    public void sort(int[] value) {
        int temp = 0;

        for (int h = value.length / 2; h > 0; h = h / 2) {
            for (int i = h; i < value.length; i++) {
                for (int j = i - h; j >= 0; j -= h) {
                    if (value[j] > value[j + 1]) {
                        temp = value[j];
                        value[j] = value[j + h];
                        value[j + h] = temp;
                    }
                }
            }
        }
    }
}

运行结果：1,2,3,4,5,5,6,7,8,9,