AcWing 787. 归并排序
原题链接
简单
作者:
haah
,
2020-12-06 10:21:35
,
所有人可见
,
阅读 341
JAVA 代码
import java.io.*;
/**
* @Author: ChangAo
* @Date: 2020/12/5 16:55
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int num = Integer.parseInt(br.readLine());
String [] res = br.readLine().split(" ");
int [] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = Integer.parseInt(res[i]);
}
merge_sort(arr,0,num-1);
for (int i : arr)
bw.write(i + " ");
bw.flush();
}
public static void merge_sort(int arr[], int l, int r)
{
if (l >= r) return; // 确定递归边界
int mid = l + r >> 1; // 1、确定分界点mid
// 2、递归左右区间
merge_sort(arr, l, mid);
merge_sort(arr, mid + 1, r);
// 3、1 定义两个指标变量
int i = l, j = mid + 1;
int k = 0; // 辅助数组位置指标
int[] tmp = new int[r - l + 1]; //辅助数组定义, 用于临时存储 [l,r]区间内排好序的数据
// 3、3循环终止条件,某个数组到达边界
while (i <= mid && j <= r){
if (arr[i] <= arr[j]) tmp[k ++ ] = arr[i ++ ];
else tmp[k ++ ] = arr[j ++ ];
}
while (i <= mid) tmp[k ++ ] = arr[i ++ ]; // 3.4 如果左区间还有元素
while (j <= r) tmp[k ++ ] = arr[j ++ ]; // 3.5 如果右区间还有元素
for (i = l, j = 0; i <= r; i ++, j ++ ) // 4. 复制回原数组
arr[i] = tmp[j];
}
}