45 lines
1.1 KiB
JavaScript
45 lines
1.1 KiB
JavaScript
/**
|
|
* @description 不修改原数组，返回新数组
|
|
* @param {number[]} left - 需要合并的左数组
|
|
* @param {number[]} right - 需要合并的右数组
|
|
*/
|
|
export function mergeSort(arr) {
|
|
if (arr.length <= 1) {
|
|
return arr; // 已经有序
|
|
}
|
|
|
|
// 分解
|
|
const middle = Math.floor(arr.length / 2);
|
|
const left = arr.slice(0, middle);
|
|
const right = arr.slice(middle);
|
|
|
|
// 递归地对左右两部分进行归并排序
|
|
const sortedLeft = mergeSort(left);
|
|
const sortedRight = mergeSort(right);
|
|
|
|
// 合并
|
|
return merge(sortedLeft, sortedRight);
|
|
}
|
|
|
|
function merge(left, right) {
|
|
const result = [];
|
|
let leftIndex = 0;
|
|
let rightIndex = 0;
|
|
|
|
// 比较两个数组的元素，将较小的元素加入结果数组
|
|
while (leftIndex < left.length && rightIndex < right.length) {
|
|
if (left[leftIndex] < right[rightIndex]) {
|
|
result.push(left[leftIndex]);
|
|
leftIndex++;
|
|
} else {
|
|
result.push(right[rightIndex]);
|
|
rightIndex++;
|
|
}
|
|
}
|
|
|
|
// 将剩余的元素加入结果数组
|
|
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
|
|
}
|
|
|
|
export default mergeSort;
|