专栏首页C++的沉思归并快排算法比较及求第K大元素
原创

归并快排算法比较及求第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 大的值即可,非常高效。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++快速排序原理深究优化

    前面写过一篇关于归并和快排的文章《归并快排算法比较及求第K大元素》,但文中实现的快排算法,在某些极端情况下时间复杂度会退化到 O(n2),效率将是无法接受的。本...

    evenleo
  • 二叉树常见算法总结和C++实现

    DFS深度搜索(从上到下)和分治法区别:前者一般将最终结果通过引用参数传入,或者一般递归返回结果最终合并

    evenleo
  • 从位图原理到布隆过滤器的实现

    假设一个int占4个字节(32位),40个亿个整数就是160亿个字节,大概相当于16GB,假设一台计算机只有2GB内存,则16GB一次加载不完,需要分8次加载,...

    evenleo
  • 一文弄懂七种排序算法

    本文介绍了七种经典排序算法,包括冒泡排序,选择排序,插入排序,希尔排序,归并排序,快速排序以及堆排序,并且讨论了各种算法的进一步改进,在文章最后还对所有算法的时...

    zhayujie
  • BFPRT算法

     首先将原数组分成5个一组,每组内进行排序,组间不排序,然后将每组的中位数取出再次进行上述操作,直到最后只能分成一组了,然后取出中位数,将这个中位数当作标尺进行...

    mathor
  • PAT (Basic Level) Practice (中文)1061 判断题

    判断题的评判很简单,本题就要求你写个简单的程序帮助老师判题并统计学生们判断题的得分。

    C you again 的博客
  • C语言 | C++动态分配与静态分配的区别

    所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间,而是由系统根...

    小林C语言
  • 13:大整数的因子

    13:大整数的因子 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 已知正整数k满足2<=k<=9,现给出长度最大为30位...

    attack
  • 动态分配与静态分配的区别

    所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间,而是由系统根...

    C语言与CPP编程
  • BZOJ3529: [Sdoi2014]数表(莫比乌斯反演 树状数组)

    \[\sum_{i = 1}^n \sum_{j = 1}^m \sigma(gcd(i, j))\]

    attack

扫码关注云+社区

领取腾讯云代金券