排序：log(n)归并，快速

1 归并排序的原理

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

写递归代码的技巧就是，分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。所以，要想写出归并排序的代码，我们先写出归并排序的递推公式。

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件：
p >= r 不用再继续分解

let merge = (arr1, arr2) => {
    let temp = []
    while(arr1.length && arr2.length){
        if(arr1[0] < arr2[0]){
            let num = arr1.shift()
            temp.push(num)
        }else{
            let num = arr2.shift()
            temp.push(num)
        }
    }
    let res
    if(arr1.length){
        res = temp.concat(arr1)
    }
    if(arr2.length){
        res = temp.concat(arr2)
    }
    return res
}
let mergeSort = (arr) => {
    let  l = 0, r= arr.length-1, p = r >> 1
    if( p >= r) return arr
    let arr1 = mergeSort(arr.slice(0,p+1))
    let arr2 = mergeSort(arr.slice(p+1,r+1))
    arr = merge(arr1, arr2)
    return arr
}
let a = [4,5,6,3,1,2]
console.log(mergeSort(a))

如图所示，我们申请一个临时数组 tmp，大小与 A[p…r]相同。我们用两个游标 i 和 j，分别指向 A[p…q]和 A[q+1…r]的第一个元素。比较这两个元素 A[i]和 A[j]，如果 A[i]<=A[j]，我们就把 A[i]放入到临时数组 tmp，并且 i 后移一位，否则将 A[j]放入到数组 tmp，j 后移一位。继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组 tmp 中的数据拷贝到原数组 A[p…r]中。
非原地，稳定，都是log（n）
**

2 快速排序的原理

快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

const quick = (arr, l, r) => {
    let i = partition(arr, l, r)
    if (i-1 > l) quick(arr, l, i-1)
    if (i+1 < r) quick(arr, i+1, r)
    return arr
}

const partition = (arr, l, r) => {
    let pivot = arr[r]
    let i = l
    for (let j = l; j <= r; j++) {
        if (arr[j] < pivot) {
            swap(arr, i, j)
            i++
        }
    }
    swap(arr, i, r)
    return i
}

const swap = (arr, i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}

let arr = [6,7,8,9,1,3,4]
quick(arr, 0, arr.length - 1)
console.log(arr)

3总结

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。同理，理解快排的重点也是理解递推公式，还有 partition() 分区函数。归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有快排应用广泛。快速排序算法虽然最坏情况下的时间复杂度是 O(n2)，但是平均情况下时间复杂度都是 O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n2) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。