AcWing 787. 归并排序 原题链接
给定你一个长度为n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~109109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
private static void mergeSort(int[] arr, int[] temp, int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(arr, temp, start, mid);
mergeSort(arr, temp, mid + 1, end);
int l = start;
int r = mid + 1;
int idx = start;
while (l <= mid && r <= end) {
if (arr[l] < arr[r]) {
temp[idx++] = arr[l++];
}else {
temp[idx++] = arr[r++];
}
}
while (l <= mid) {
temp[idx++] = arr[l++];
}
while (r <= end) {
temp[idx++] = arr[r++];
}
System.arraycopy(temp, start, arr, start, end - start + 1);
}
AcWing 788. 逆序对的数量 原题链接
private static void countNumber(int[] arr, int[] temp, int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
int l = start;
int r = mid + 1;
int idx = start;
countNumber(arr, temp, start, mid);
countNumber(arr, temp, mid + 1, end);
while (l <= mid&& r <= end) {
if (arr[l] <= arr[r]) {
temp[idx++] = arr[l++];
} else {
res += mid - l + 1;
temp[idx++] = arr[r++];
}
}
while (l <= mid ) {
temp[idx++] = arr[l++];
}
while (r <= end) {
temp[idx++] = arr[r++];
}
System.arraycopy(temp, start, arr, start, end - start + 1);
}