AcWing 3638. 排序-JavaScript
原题链接
简单
作者:
semicloud
,
2024-03-25 17:16:26
,
所有人可见
,
阅读 1
const fs = require('fs');
const arr = fs.readFileSync(0, 'utf-8').trim().split('\n')[1].split(' ').
map((x) => parseInt(x));
mergeSort(arr, 0, arr.length - 1);
console.log(arr.join(' '));
function mergeSort(arr, l, r) {
if (l >= r) return;
// 确定分界点
const mid = l + r >> 1;
// 递归排序左边数组和右边数组,使左右两边数组都有序
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
let i = l, j = mid + 1;
// 辅助数组
const tmp = [];
// 开始归并
while (i <= mid && j <= r) {
// 两个数奇偶性相同,谁小谁在前面
if (arr[i] % 2 === arr[j] % 2) {
tmp.push(arr[i] < arr[j] ? arr[i++] : arr[j++]);
} else {
// 否则,谁是奇数谁在前面
tmp.push(arr[i] % 2 ? arr[i++] : arr[j++]);
}
}
// 处理未归并的部分
while (i <= mid) tmp.push(arr[i++]);
while (j <= r) tmp.push(arr[j++]);
// 将排好序的元素从辅助数组复制回原数组
for (let k = 0; k < tmp.length; ++k)
arr[k + l] = tmp[k];
}