归并快排算法比较及求第K大元素
原创
归并排序
核心思想：将数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两个部分有序合并在一起，这样整个数组有序。全文图示来源于王争的《数据结构和算法之美》
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，讲一个大的问题分解成小的问题来解决，小的问题解决了大的问题也就解决了。分治算法一般都是用递归来实现，分治是一种解决问题的处理思想，递归是一种编程技巧，两者并不冲突。以下重点讨论如何用递归代码来实现归并排序。下面是归并排序的递推公式。
递推公式：
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 大的值即可，非常高效。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
