-
-
Notifications
You must be signed in to change notification settings - Fork 229
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
归并排序 #197
Comments
|
/**
* 归并排序
* @param arr 待排序数组
* @returns
*/
const mergeSort = function (arr: number[]): number[] {
const len = arr.length;
// 当被分割的数组只有一个元素时,返回数组。
if (len <= 1) return arr;
const mid = Math.floor(len / 2);
const leftArr = mergeSort(arr.slice(0, mid));
const rightArr = mergeSort(arr.slice(mid, len));
arr = mergeArr(leftArr, rightArr);
return arr;
};
/**
* 合并两个有序数组
* @param leftArr
* @param rightArr
* @returns
*/
const mergeArr = function (leftArr: number[], rightArr: number[]): number[] {
// 初始化两个指针,分别指向 arr1 和 arr2
let i = 0;
let j = 0;
const res: number[] = [];
while (i < leftArr.length && j < rightArr.length) {
if (leftArr[i] <= rightArr[j]) {
res.push(leftArr[i]);
i++;
} else {
res.push(rightArr[j]);
j++;
}
}
// 若其中一个子数组会首先被合并完全,则直接拼接另一个子数组的剩余部分
if (i < leftArr.length) {
return [...res, ...leftArr.slice(i)];
} else {
return [...res, ...rightArr.slice(j)];
}
};
// test
const arr = [8, 7, 6, 5, 4, 3, 2, 1];
console.log(mergeSort(arr)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
No description provided.
The text was updated successfully, but these errors were encountered: