归并排序

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了

归并排序和快速排序都用到了分治思想，非常巧妙。我们可以借鉴这个思想，来解决非排序的问题，比如:如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素? 这就要用到我们今天要讲的内容。

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

解法

const mergeArr = (left, right) => {
    let temp = []
    let leftIndex = 0
    let rightIndex = 0
    // 判断2个数组中元素大小，依次插入数组
    while (left.length > leftIndex && right.length > rightIndex) {
        if (left[leftIndex] <= right[rightIndex]) {
            temp.push(left[leftIndex])
            leftIndex++
        } else {
            temp.push(right[rightIndex])
            rightIndex++
        }
    }
    // 合并 多余数组
    return temp.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}

const 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)
    // 递归 分解 合并
    return mergeArr(mergeSort(left), mergeSort(right))
}

const testArr = []
let i = 0
while (i < 100) {
    testArr.push(Math.floor(Math.random() * 1000))
    i++
}

const res = mergeSort(testArr)
console.log(res)

一直没懂归并和快速排序的区别，现在看来区分如下

归并区分是从长度上不断把当前的数组划分为两部分，然后每部分继续划分然后使用mergeArr来合并，也就是划分到最后只有两个的时候，使用比大小来调换位置，然后继续开始往上合并。

而快速排序是找到一个值，然后比当前值大的划分到一部分，比当前值小的划分到一部分，然后每一部分继续通过这种方式来划分，划分到最后不能划分后，就开始往上合并

FilesExpand file tree

merge.md

Latest commit

History

merge.md

File metadata and controls

归并排序

解法