归并排序
给你一个整数数组 nums,请你将该数组升序排列。
原理
归并排序利用了分治的思想来对序列进行排序。对一个长为 n 的待排序的序列,我们将其分解成两个长度为n/2的子序列。每次先递归调用函数使两个子序列有序,然后我们再线性合并两个有序的子序列使整个序列有序。
相关属性
- 递归实现
- 缺点:
- 容易爆栈,当数组足够大,递归很深
- 需要额外的内存空间
- 优点
- 性能不受输入数据的影响,始终都是 O(nlogn) 的时间复杂度
- 稳定的排序算法
- 缺点:
递归实现
js
/**
* 归并排序
* @param {Array<number>} arr
*/
function mergeSort(arr) {
const len = arr.length
// 无需排序
if (len < 2) {
return arr
}
const mid = len >> 1 // 右移一位 === 除2并向下取整
return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}
/**
* 合并
* @param {Array<number>} left
* @param {Array<number>} right
*/
function merge(left, right) {
const res = []
let i = 0, j = 0
while (i < left.length && j < right.length) {
res.push(left[i] <= right[j] ? left[i++] : right[j++])
}
while (i < left.length) {
res.push(left[i++])
}
while (j < right.length) {
res.push(right[j++])
}
return res
}
/**
* 归并排序
* @param {Array<number>} arr
*/
function mergeSort(arr) {
const len = arr.length
// 无需排序
if (len < 2) {
return arr
}
const mid = len >> 1 // 右移一位 === 除2并向下取整
return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}
/**
* 合并
* @param {Array<number>} left
* @param {Array<number>} right
*/
function merge(left, right) {
const res = []
let i = 0, j = 0
while (i < left.length && j < right.length) {
res.push(left[i] <= right[j] ? left[i++] : right[j++])
}
while (i < left.length) {
res.push(left[i++])
}
while (j < right.length) {
res.push(right[j++])
}
return res
}
迭代实现
js
//TODO: ... 未完待续
//TODO: ... 未完待续