本篇文章为你整理了AcWing 787.归并排序（Java）（）的详细内容，包含有 AcWing 787.归并排序（Java），希望能帮助你了解 AcWing 787.归并排序（Java）。
题目来源：https://www.acwing.com/problem/content/description/789/
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出共一行，包含 n 个整数，表示排好序的数列。
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
首先确定中间基准点mid = left + （right - left） / 2，在每次进行方法时先进性一次递推进行数组的分割，将数组分为单个值后进行排序，在对每个小数组及进行归并，最后归并为一个排好序的数组
那么如何进行排序呢？我们应当确定的是，先经过递推后的输皆为单个数，那么二者进行比较后将该数存入临时数组中即可。这样我们就得到了两两成对的数组。然后我们再进行判断，例如数组a1,a2,b1,b2，首先我们应确定的是a1 a2,b数组同理。那么我们便要将两个数组中较小的值，也就是靠前的值进行比较，然后再接着比··· ···直到整个数组合并完成。
需要注意的是，为了防止某一段数组的长度大于另一端，需加入判断语句，将剩下的值一起存入临时数组（因为剩下的值也是排序好的，直接加进去就好）
import java.util.Scanner;
public class Main {
//开辟足够大的数组空间
static int N = 100010;
static int[] q = new int[N], temp = new int[N];
public static void main(String[] args) {
//输入数组大小以及数组的值
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i i++) {
q[i] = sc.nextInt();
//进行排序
merge_sort(q,0,n-1);
//输出结果
for(int i = 0; i i ++) System.out.print(q[i] + " ");
public static void merge_sort(int []q,int left,int right) {
//进行判断
if (left = right) return;
//进行递归，将数组分为最小单位的值,接着在从最小进行排序，逐渐到整个数组
int mid = left + (right - left) / 2;
merge_sort(q, left, mid);
merge_sort(q, mid + 1, right);
int i = left, j = mid + 1;//建立双指针，i指向前一个数，j指向后一个数
int k = 0;//令temp从0开始，往其中添加元素
//进行归并操作，将数存放至临时数组temp
while (i = mid j = right) {//确认边界
if (q[i] = q[j])
temp[k++] = q[i++];
else
temp[k++] = q[j++];
//防止i或j提前用光的情况发生
while (i = mid) temp[k++] = q[i++];
while (j = right) temp[k++] = q[j++];
for(i = left, k = 0; i = right; i ++, k ++) q[i] = temp[k];//把原数组未排序的部分覆盖成已排序部分
while (i = mid j = right) {//确认边界
if (q[i] = q[j])
temp[k++] = q[i++];
else
temp[k++] = q[j++];
在这里我将if-else中的temp[k++] = q[i++]与temp[k++] = q[j++]中的q全部失误写成了temp，直接导致结果中出现了不该存在的“0”，查了好几遍才发现······
以上就是AcWing 787.归并排序（Java）（）的详细内容，想要了解更多 AcWing 787.归并排序（Java）的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。