AcWing 787. 归并排序
原题链接
简单
作者:
啊混
,
2024-03-25 21:52:45
,
所有人可见
,
阅读 1
JAVA
package Merge;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
/*给定你一个长度为 n
的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n
第二行包含 n
个整数(所有整数均在 1∼109
范围内),表示整个数列。
输出格式
输出共一行,包含 n
个整数,表示排好序的数列。*/
public class Main02 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n =scanner.nextInt();
int [] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = scanner.nextInt();
}
int[] after = sortArray(num);
for (int i = 0; i < num.length; i++) {
System.out.print(after[i] + " ");
}
}
private static int[] sortArray(int[] num){
int len = num.length;
int[] temp = new int[len];
magersort(num,0,len-1,temp);
return num;
}
public static void magersort(int[] num, int left, int right, int[] temp) {
if (left == right){ //拆分成最小的元素后,直接返回
return ;
}
int mid = (right + left) /2 ;
magersort(num,left,mid,temp);
magersort(num,mid +1,right,temp);
for (int i = left; i <= right ; i++) {
temp[i] = num[i];
}
int i = left;
int j = mid +1;
for (int k = left; k <= right; k++){
if (i>mid){
num[k] = temp[j];
j++;
}
else if(j>right){
num[k] = temp[i];
i++;
}
else if(temp[i]<temp[j]){
num[k] = temp[i];
i++;
}
else{
num[k] = temp[j];
j++;
}
}
}
}