Java高级排序_java中public void sort(int[] array)是什么

1.希尔排序

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

排序原理：

1. 选定一个增长量h(可以为数组长度一半开始)，按照增长量h作为数据分组的依据，对数据进行分组；

2. 对分好组的每一组数据完成插入排序；

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

    //希尔排序
    public static void sort(int[] arr) {
        //增长量
        int h = arr.length / 2;
        while (h > 0) {
            for (int i = h; i < arr.length; i++) {
                int j = i, temp = arr[j];
                while (j - h >= 0 && temp < arr[j - h]) {
                    //数组后退
                    arr[j] = arr[j - h];
                    j -= h;
                }
                //向前交换插入
                arr[j] = temp;
            }
            //每次将分隔量减半
            h /= 2;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一 部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序 过程可以递归进行，以此达到整个数据变成有序序列。

排序原理：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分；

2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于 或等于分界值，而右边部分中各元素都大于或等于分界值；

3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两 部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当 左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

    //快速排序
    public static void sort(int[] arr, int left, int right) {
        int leftTemp = left, rightTemp = right;
        int center = arr[right - (right - left) / 2];
        while (left < right) {
            //左边找到比中间值大的停止循环，如果没有则到center退出
            while (arr[left] < center) {
                left += 1;
            }
            //右边找到比中间值小的停止循环，如果没有则到center退出
            while (arr[right] > center) {
                right -= 1;
            }
            //结束while循环
            if (left >= right) {
                break;
            }
            //进行左右交换
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            //避免左边值等于中间值,将中间值交换过去，要将右边指针左移一位，避免死循环
            if (arr[left] == center) {
                right -= 1;
            }
            //避免右边值等于中间值,将中间值交换过去，要将左边指针左移一位，避免死循环
            if (arr[right] == center) {
                left += 1;
            }
        }
        //避免栈溢出
        if (left == right) {
            left += 1;
            right -= 1;
        }
        //向左递归
        if (leftTemp < right) {
            sort(arr, leftTemp, right);
        }
        //向右递归
        if (left < rightTemp) {
            sort(arr, left, rightTemp);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3.归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子 序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序 表，称为二路归并。

排序原理：

1. 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1为止。

2. 将相邻的两个子组进行合并成一个有序的大组；

3. 不断的重复步骤2，直到最终只有一个组为止。

    //归并排序
    public static void sort(int[] arr, int left, int right) {
        if (left < right) {
            //创建临时数组
            int[] temp = new int[right - left + 1];
            int center = left + (right - left) / 2;  //获取中间索引
            //向左递归
            sort(arr, left, center);
            //向右递归
            sort(arr, center + 1, right);
            sort(arr, left, center, right, temp);
        }
    }

    /**
     * 具体排序合并方法
     *
     * @param arr    排序数组
     * @param left   左边界
     * @param center 中间分界线
     * @param right  右边界
     * @param temp   临时数组,用来copy和排序数组
     */
    private static void sort(int[] arr, int left, int center, int right, int[] temp) {
        //定义左指针,左终点为center,并且定义右指针
        int leftTemp = left, rightTemp = center + 1;
        //临时数组遍历指针
        int tempStart = 0;
        //对俩边数组比较遍历，丢入临时数组中(结束条件为左边指针或者右边指针一个遍历结束)
        while (leftTemp <= center && rightTemp <= right) {
            //判断丢入临时数组
            if (arr[leftTemp] > arr[rightTemp]) {
                temp[tempStart] = arr[rightTemp];
                rightTemp++;
                tempStart++;
            } else {
                temp[tempStart] = arr[leftTemp];
                leftTemp++;
                tempStart++;
            }
        }
        //遍历左边可能剩余的数组元素
        while (leftTemp <= center) {
            temp[tempStart] = arr[leftTemp];
            leftTemp++;
            tempStart++;
        }
        //遍历右边可能剩余的数组元素
        while (rightTemp <= right) {
            temp[tempStart] = arr[rightTemp];
            rightTemp++;
            tempStart++;
        }
        //temp数组指针从头开始
        tempStart = 0;
        //将temp数组排序好的数组copy到要排序的数组中
        for (int i = left; i <= right; i++) {
            arr[i] = temp[tempStart++];
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60