数据结构-归并排序Java实现

一、引言

    归并排序是一种建立在归并操作上的有效、稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

二、算法步骤

归并排序的核心思想是将数组分为两个子数组，然后递归地对这两个子数组进行排序，最后将它们合并为一个有序的数组。具体步骤如下：

1. 分割：将数组分为两个子数组，通常是平均分割。
2. 递归排序：对这两个子数组分别应用归并排序。
3. 合并：将两个已排序的子数组合并为一个有序的数组。
4. 这个过程重复进行，直到整个数组都排好序。

三、原理演示

假设我们有一个未排序的整数数组：
[38, 27, 43, 3, 9, 82, 10]

第一步：分割

在第一步中，我们将数组分割为两个大致相等的子数组。这是归并排序的分治策略的开始。
左子数组： [38, 27, 43]
右子数组： [3, 9, 82, 10]

第二步：递归排序

现在，我们递归地对左子数组和右子数组进行排序。这意味着我们会进一步分割这些子数组，然后再次排序。
对左子数组排序：
左子数组 [38, 27, 43] 分割为：
左子数组： [38]
右子数组： [27, 43]
递归排序右子数组 [27, 43]，将其分割为 [27] 和 [43]。现在，对这两个子数组进行合并排序。
对右子数组排序：
右子数组 [3, 9, 82, 10] 分割为：
左子数组： [3, 9]
右子数组： [82, 10]
递归排序左子数组 [3, 9]，将其分割为 [3] 和 [9]。然后，递归排序右子数组 [82, 10]，将其分割为 [82] 和 [10]。接下来，对这四个子数组进行合并排序。

第三步：合并

在这一步中，我们将已排序的子数组合并成一个更大的有序数组。首先，我们合并左边的两个子数组 [3] 和 [9]，形成 [3, 9]。然后，我们合并右边的两个子数组 [10] 和 [82]，形成 [10, 82]。
现在，我们将左边的 [3, 9] 和右边的 [10, 82] 合并成一个有序数组 [3, 9, 10, 82]。接下来，我们将左边的 [27, 43] 和右边的 [3, 9, 10, 82] 合并成一个更大的有序数组：
左子数组： [27, 43]
右子数组： [3, 9, 10, 82]
再次，我们将这两个有序数组合并为整个已排序的数组：
[3, 9, 10, 27, 43, 82]
最终我们就得到了这个有序数组。

四、代码实战

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        System.out.println("原始数组：");
        printArray(arr);

        mergeSort(arr);

        System.out.println("排序后的数组：");
        printArray(arr);
    }

    public static void mergeSort(int[] arr) {
        int n = arr.length;
        if (n > 1) {
            int mid = n / 2;
            int[] left = new int[mid];
            int[] right = new int[n - mid];

            for (int i = 0; i < mid; i++) {
                left[i] = arr[i];
            }
            for (int i = mid; i < n; i++) {
                right[i - mid] = arr[i];
            }

            mergeSort(left);
            mergeSort(right);

            merge(arr, left, right);
        }
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int n1 = left.length;
        int n2 = right.length;
        int i = 0, j = 0, k = 0;

        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
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

上述代码演示了归并排序的实现。它首先定义了一个包含整数数组的示例，然后调用 mergeSort 方法来对数组进行排序。mergeSort 方法使用递归将数组分解为更小的子数组，然后调用 merge 方法将这些子数组合并为有序的数组。

五、结论

我们一起来总结一下：

1. 归并排序的时间复杂度为O(nlogn)，其中n是待排序元素的个数。这主要是因为归并排序在每次递归中都会将问题规模缩小为原来的一半，同时在合并两个有序子序列时需要进行一次线性扫描。
2. 归并排序的空间复杂度为O(n)，因为需要额外的空间存储归并过程中的临时数组。
3. 归并排序是一种稳定的排序算法，即相同元素的相对位置在排序后不会改变。
4. 归并排序可以很好地利用缓存，因为其每次只对一个子序列进行排序，这有利于减少缓存未命中的概率。

点赞收藏，富婆包养✋✋