归并排序

核心思想：将数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两个部分有序合并在一起，这样整个数组有序。全文图示来源于王争的《数据结构和算法之美》

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，讲一个大的问题分解成小的问题来解决，小的问题解决了大的问题也就解决了。分治算法一般都是用递归来实现，分治是一种解决问题的处理思想，递归是一种编程技巧，两者并不冲突。以下重点讨论如何用递归代码来实现归并排序。下面是归并排序的递推公式。

递推公式：
merge_sort(p...r) = merge(mergesort(p...q), mergesort(q+1...r))

终止条件：
p >= r 不用继续分解

mergesort(p...r) 表示给下标从 p 到 r 之间的数组排序。将这个排序问题转化为两个子问题 mergesort(p...q) 和mergesort(q+1...r)，其中 q 为 p 和 r 的中间位置，即(p+r)/2。当前后两个子数组排好序之后，再将它们合并在一起，这样下标从 p 到 r 之间的数据也就排序好了。具体过程用C++实现如下：

void mergesort(vector<int>& A, int l, int r)
{
    if (l < r) 
    {
        int mid = l + (r - l) / 2;
        mergesort(A, l, mid);
        mergesort(A, mid+1, r);
        merge(A, l, mid, r);
    }
}

void merge(vector<int>& A, int l, int mid, int r) 
{
    vector<int> tmp(r - l + 1);
    int i = l;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r) {
        tmp[k++] = A[i] < A[j] ? A[i++] : A[j++];
    } 
    while (i <= mid) {
        tmp[k++] = A[i++];
    }
    while (j <= r) {
        tmp[k++] = A[j++];
    }
    
    for (i = l, k = 0; i <= r; ++i, ++k) 
        A[i] = tmp[k];
}

归并排序的时间复杂度任何情况下都是 O(nlogn)，看起来非常优秀（快速排序最坏情况系时间复杂度也是 O(n2)）。但归并排序并没有像快排那样应用广泛，因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。原因是合并函数需要借助额外的存储空间，空间复杂度为 O(n)。

快速排序

核心思想：选取一个基准元素 pivot，比 pivot 小的放到左边，比 pivot 大的放到右边，对 pivot 左右两边的序列递归进行以上操作。

快速排序也是根据分治、递归的处理思想实现。地推公式如下：

递推公式：
quicksort(p…r) = quicksort(p…q-1) + quicksort(q+1...r)

终止条件：
p >= r

在wikipedia看到一个比较好的快速排序实现，这里用C++实现一遍，这里的 partition 非常巧妙而且容易理解，取最后元素为基准 pivot，i 开始取值 l，j 从 l 遍历至 h-1，当 A[j] < pivot 时，交换 A[i] 和 A[j] 的值，同时 i++，实现将小于 pivot 的值全部放在区间[l, i)中，跳出循环体后将 A[i] 和 A[h] 值交换，至此，(i,r] 区间的值都不小于 pivot，返回 pivot 的索引。讲的比较啰嗦，直接看代码并推敲一下过程应该也容易弄懂。

void quicksort(vector<int>& A, int l, int r) 
{
    if (l < r) 
    {
        int p = partition(A, l, r);
        quicksort(A, l, p-1);
        quicksort(A, p+1, r);
    }
}

int partition(vector<int>& A, int l, int r)
{
    int pivot = A[r];
    int i = l;
    for (int j = l; j < r; ++j)
    {
        if (A[j] < pivot) {
            std::swap(A[i++], A[j]);
        }
    }
    std::swap(A[i], A[r]);
    return i;
}

快速排序的算法的平均时间复杂度是 O(nlogn)，最坏时间复杂度是 O(n2)，空间复杂度是 O(1)。快速排序不是一个稳定的排序算法。

归并排序和快速排序的区别

由上图可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后合并。而快排正好相反，其处理过程是由上而下的，先分区，然后处理子问题。归并排序虽然是稳定的，时间复杂度是 O(nlogn) 的排序算法，但它是非原地排序算法。快排通过设计巧妙的原地分区函数，可以实现原地排序，解决归并排序占用太多内存的问题。

快排思想求第K大元素

利用快排思想可以实现O(n)时间复杂度内求无序数组中的第 K 大元素，LeetCode题目215. 数组中的第K个最大元素，具体实现如下：

class Solution {
public:
    int findKthLargest(vector<int>& A, int k) {
        return get_top_k(A, 0, A.size()-1, k);
    }
    int get_top_k(vector<int>& A, int l, int r, int k)
    {
        int p = partition(A, l, r);
        if (k-1 == p) return A[p];  // 索引从0开始，第k大需减一
        return k-1 < p ? get_top_k(A, l, p-1, k) 
                    : get_top_k(A, p+1, r, k);
    }
    int partition(vector<int>& A, int l, int r)
    {
        int pivot = A[r];
        int i = l;
        for (int j = l; j < r; ++j)
        {
            if (A[j] > pivot) {
                std::swap(A[i++], A[j]);
            }
        }
        std::swap(A[i], A[r]);
        return i;
    }
};

非常巧妙，修改了 partition 函数的实现，左边放大于基准的元素，而且不需要将数组全部排序，只要求出第 k 大的值即可，非常高效。