归并排序（Merge Sort）

将每个元素两两合并，进行内部排序，逐渐合并成一个集合，达到有序

package com.zsl.datastructalgorithm.date20220628;

import java.util.Arrays;

/**
 * 归并排序
 *      采用分治思想，逐渐有序
 *
 * @author zsl
 * @date 2022/6/28 21:43
 * @email 249269610@qq.com
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] elements = new int[]{132, 45, 345, 65, 77, 876, 23, 645, 66, 58};


        int[] ints1 = {5, 6};
        int[] ints2 = {6, 5};
        sort(elements);
        sort(ints1);
        sort(ints2);

        System.out.println(Arrays.toString(ints1));
        System.out.println(Arrays.toString(ints2));
        System.out.println(Arrays.toString(elements));
    }

    public static void sort(int[] elements) {
        if (elements.length < 2) return ;

        mergeSort(elements, 0, elements.length - 1);
    }

    /**
     * 归并逻辑
     *
     * @param elements 元素数组
     * @param start    起始索引
     * @param end      结束索引
     */
    private static void mergeSort(int[] elements, int start, int end) {
        int size = end - start;
        if (size <= 0) return ;

        int half = (start + end) / 2;

        // 分治
        mergeSort(elements, start, half);
        mergeSort(elements, half + 1, end);

        int[] tmp = new int[size + 1];
        int leftIndex = start;
        int rightIndex = half + 1;
        int leftLen = half - start + 1;
        int rightLen = end - half;
        // 比较并插入排序
        for (int i = 0; i < size + 1; i++) {
            if (leftIndex - half == 1) {
                tmp[i] = elements[rightIndex++];
                continue;
            }

            if (rightIndex - end == 1) {
                tmp[i] = elements[leftIndex++];
                continue;
            }


            if (elements[leftIndex] < elements[rightIndex]) {
                tmp[i] = elements[leftIndex++];
            } else {
                tmp[i] = elements[rightIndex++];
            }
        }

        // 写回原数组
        System.arraycopy(tmp, 0, elements, start, rightLen + leftLen);
    }
}
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

快速排序（Quick Sort）

将一个集合分成整体有序但两个无序集合，再对无序集合进行排序成两个集合，从而达成有序集合

package com.zsl.datastructalgorithm.date20220628;

import java.util.Arrays;

/**
 * 快速排序
 *      采用分治思想，逐渐有序
 *
 * @author zsl
 * @date 2022/6/28 21:02
 * @email 249269610@qq.com
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] elements = new int[]{132, 45, 345, 65, 77, 876, 23, 645, 66, 58};

        sort(elements);
        int[] ints1 = {5, 6};
        int[] ints2 = {6, 5};
        sort(ints1);
        sort(ints2);
        System.out.println(Arrays.toString(elements));
    }

    public static void sort(int[] elements) {
        if (elements.length < 2) {
            return;
        }

        quickSort(elements, 0, elements.length - 1);
    }

    /**
     * 递归执行
     * @param elements 元素数组
     * @param start 起始索引
     * @param end 结束索引
     */
    public static void quickSort(int[] elements, int start, int end) {
        if (end - start <= 0) return;

        // 排序
        int left = start;
        int right = start;

        // 将最后一位当中心值
        int pivot = elements[end];
        int cnt = end - start;
        for (int i = 0; i < cnt; i++) {
            if (elements[right] <= pivot) {
                swap(elements, left, right);
                ++left;
                ++right;
            } else {
                ++right;
            }
        }

        // 将轴移动到中心
        int tmp = elements[left];
        elements[left] = elements[right];
        elements[right] = tmp;

        // 左侧集合
        quickSort(elements, start, left - 1);
        // 右侧集合
        quickSort(elements, left + 1, end);
    }

    /**
     * 交换指定索引元素
     * @param elements 待交换数组
     * @param left
     * @param right
     */
    private static void swap(int[] elements, int left, int right) {
        if (left == right) return;

        int tmp = elements[left];
        elements[left] = elements[right];
        elements[right] = tmp;
    }
}
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

关系

都是采用分治的思想，归并是自底向上逐渐有序，快排是自顶向下逐渐有序