大家好，我是何未来，本篇文章给大家讲解《AcWing算法基础课》787 题——归并排序。本文详细介绍了归并排序的算法思路，包括分解、合并和递归排序三个主要步骤。通过 Java 代码实现，展示了如何将数组递归分解至单个元素，再逐步合并成有序数组。
文章目录
❓题目描述?算法思路✅Java代码?参考
❓题目描述
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000输入样例：
53 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, jwhile (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算法基础课