归并排序思想

  1. 取一个基准点, 将数组不断拆分成左右两部分, 直到数组的长度为 1;
  2. 对拆离的数组进行比较合并;

演示如下:

3 1 5 2
3 1 | 5 2
3 | 1 | 5 | 2
1 3 | 2 5
1 2 3 5

代码实现

// 可以把它当成分函数
var mergeSort = function(arr) {
// 将数组 arr 拆分成 [0, point) 和 [point, arr.length] 两部分
const point = arr.length / 2
const left = arr.slice(0, point)
const right = arr.slice(point, arr.length)
if (arr.length === 1) {
return arr
}
return merge(mergeSort(left), mergeSort(right))
}
// 可以当作是合函数
function merge(left, right) {
let l = 0 // 第一个数组的下标
let r = 0 // 第二个数组的下标
const result = []
while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
result.push(left[l])
l++
} else {
result.push(right[r])
r++
}
}
while (l < left.length) {
result.push(left[l])
l++
}
while (r < right.length) {
result.push(right[r])
r++
}
return result
}

归并排序与快速排序的异同

归并排序与快速排序都是用递归来实现的算法, 都是分分合合的过程。区别在于归并排序在合的过程中进行排序, 快速排序则在分的过程中进行排序。另外它们的时间复杂度都为 O(nlogn)。