Java版归并排序（合并排序）_合并算法java

分析&回答

---

看不懂的话看下面动画展示！

图像展示

拆分阶段

排序阶段

实现代码

/**
 * 归并排序
 * <p>
 * 分而治之(divide - conquer);每个递归过程涉及三个步骤
 * 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
 * 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
 * 第三, 合并: 合并两个排好序的子序列,生成排序结果.
 *
 * @param a
 * @param low
 * @param high
 * @return
 */
public static int[] mergeSort(int[] a, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        //左右归并
        merge(a, low, mid, high);
    }
    return a;
}

public static void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;
    int j = mid + 1;
    int k = 0;
    // 把较小的数先移到新数组中
    while (i <= mid && j <= high) {
        if (a[i] < a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    // 把左边剩余的数移入数组
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    // 把右边边剩余的数移入数组
    while (j <= high) {
        temp[k++] = a[j++];
    }
    // 把新数组中的数覆盖nums数组
    for (int x = 0; x < temp.length; x++) {
        a[x + low] = temp[x];
    }
}
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

动画演示

性能分析

• 稳定
• 平均时间复杂度O(n ㏒n)
• 空间复杂度O(n)

反思&扩展

---

Java版常用排序算法复杂度

---

喵呜面试助手： 一站式解决面试问题，你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享！