AcWing 787. 归并排序
原题链接
简单
作者:
将情怀讲泛滥的恶果
,
2021-05-17 16:34:00
,
所有人可见
,
阅读 326
java
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
InputStreamReader in=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(in);
int num = Integer.parseInt(br.readLine());
int[] arrs = new int[num];
String[] res=br.readLine().split(" ");
for(int i=0;i<res.length;i++){
arrs[i]=Integer.parseInt(res[i]);
}
merge_sort(arrs,0,arrs.length-1);
for(int i=0;i<arrs.length;i++){
System.out.print(arrs[i]+" ");
}
}
public static void merge_sort(int[] nums, int left, int right) {
if (left >= right) return;
int mid = (left + right) >> 1;
merge_sort(nums, left, mid);
merge_sort(nums, mid + 1, right);
int[] temp = new int[right - left + 1];
int l = left;
int r = mid + 1;
int i = 0;
while (l <= mid && r <= right) {
if (nums[l] <= nums[r]) {
temp[i] = nums[l];
l += 1;
} else {
temp[i] = nums[r];
r += 1;
}
i += 1;
}
while (r <= right) {
temp[i] = nums[r];
r += 1;
i += 1;
}
while (l <= mid) {
temp[i] = nums[l];
l += 1;
i += 1;
}
for (int k = 0; k < right - left + 1; k++) {
nums[left + k] = temp[k];
}
}
}