大家好，我是何未来，本篇文章给大家讲解《AcWing算法基础课》787 题——归并排序。本文详细介绍了归并排序的算法思路，包括分解、合并和递归排序三个主要步骤。通过 Java 代码实现，展示了如何将数组递归分解至单个元素，再逐步合并成有序数组。

文章目录

❓题目描述💡算法思路✅Java代码🔗参考

❓题目描述

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10⁹ 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

<code>1≤n≤100000

输入样例：

5

3 1 2 4 5

输出样例：

1 2 3 4 5

💡算法思路

分解：将数组从中间分成两个子数组，直到每个子数组只包含一个元素。这一步通过递归实现，确保每个子数组都是有序的（单个元素自然是有序的）。合并：将两个有序的子数组合并成一个有序的数组。这一步是归并排序的关键。合并过程中，程序会比较两个子数组中的元素，按顺序将较小的元素放入临时数组中，直到所有元素都被合并。递归排序：在递归的每一层，程序都会对分解后的子数组进行排序，然后合并结果。最终，整个数组会被排序。

具体实现步骤：

基本检查：首先，检查传入的数组部分是否只有一个元素或为空。如果是，则不需要进一步排序，直接返回。计算中间位置：计算当前数组部分的中间位置，这个中间位置将用于将数组分成两部分。递归排序左半部分：对数组的左半部分（从左边界到中间位置）进行递归排序。递归排序右半部分：对数组的右半部分（从中间位置的下一个位置到右边界）进行递归排序。初始化合并变量：初始化三个变量：k用于跟踪临时数组的索引，i用于遍历左半部分的数组，j用于遍历右半部分的数组。合并两个有序数组：比较左半部分和右半部分的元素，将较小的元素放入临时数组tmp中，直到其中一个部分的元素全部放入临时数组。处理左半部分剩余元素：如果左半部分还有剩余元素，将它们全部放入临时数组。处理右半部分剩余元素：如果右半部分还有剩余元素，将它们全部放入临时数组。将临时数组复制回原数组：将临时数组tmp中的元素复制回原数组a的相应位置，完成合并排序。

时间复杂度：O(n log n)

空间复杂度：O(n)

稳定排序：在合并过程中，相等元素的次序保持不变。

✅Java代码

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.StreamTokenizer;

public class Aw787 {

// 创建一个StreamTokenizer用于读取输入

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

// 读取下一个整数的方法

static int nextInt() throws IOException {

in.nextToken();

return (int) in.nval;

}

static int n; // 存储数组的大小

static int[] nums = new int[100000 + 10]; // 存储输入的数组，预留一些额外的空间

static int[] tmp = new int[100000 + 10]; // 临时数组，用于合并排序

public static void main(String[] args) throws IOException {

n = nextInt(); // 读取数组的大小

for (int i = 0; i < n; i++) {

nums[i] = nextInt(); // 读取数组的每个元素

}

mergeSort(0, n - 1, nums); // 调用归并排序方法对数组进行排序

for (int i = 0; i < n; i++) {

System.out.print(nums[i] + " "); // 输出排序后的数组

}

}

// 归并排序方法，参数为数组的起始和结束索引，以及数组本身

static void mergeSort(int l, int r, int[] a) {

if (l >= r) { // 如果起始索引大于或等于结束索引，则直接返回

return;

}

int mid = l + r >> 1; // 计算中间索引

mergeSort(l, mid, a); // 递归排序左半部分

mergeSort(mid + 1, r, a); // 递归排序右半部分

// i表示左子数组的起始位置，j表示右子数组的起始位置

// k表示tmp的结束位置

int k = 0, i = l, j = mid + 1; // 初始化指针k, i, j

while (i <= mid && j <= r) { // 合并两个有序子数组

if (a[i] <= a[j]) { // 如果左半部分的元素小于或等于右半部分的元素

tmp[k++] = a[i++]; // 将左半部分的元素放入临时数组

} else {

tmp[k++] = a[j++]; // 否则将右半部分的元素放入临时数组

}

}

while (i <= mid) { // 如果左半部分还有剩余元素

tmp[k++] = a[i++]; // 将剩余元素放入临时数组

}

while (j <= r) { // 如果右半部分还有剩余元素

tmp[k++] = a[j++]; // 将剩余元素放入临时数组

}

for (i = l, j = 0; i <= r; i++, j++) { // 将临时数组中的元素复制回原数组

a[i] = tmp[j];

}

}

}

🔗参考

https://www.acwing.com/problem/content/789/https://www.hello-algo.com/chapter_sorting/merge_sort/

作者：程序员何未来-heweilai.com

🔍推荐阅读

AcWing算法基础课-786第k个数-Java题解AcWing算法基础课-785快速排序-Java题解【七夕节实践】把爱心代码放在自己的网站上是什么体验？

欢迎关注我的博客：@程序员何未来，持续为你输出有价值的技术文章~

你们的点赞👍 收藏⭐ 留言🗨️ 关注✅

是我持续创作，输出优质内容的最大动力！谢谢！

文章关键词：算法，计算机算法，算法题解，算法竞赛，Java，数据结构，AcWing算法基础课