数据结构与算法之美
王争
前 Google 工程师
280067 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?

上一节我讲了冒泡排序、插入排序、选择排序这三种排序算法,它们的时间复杂度都是 O(n2),比较高,适合小规模数据的排序。今天,我讲两种时间复杂度为 O(nlogn) 的排序算法,归并排序快速排序。这两种排序算法适合大规模的数据排序,比上一节讲的那三种排序算法要更常用。
归并排序和快速排序都用到了分治思想,非常巧妙。我们可以借鉴这个思想,来解决非排序的问题,比如:如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素? 这就要用到我们今天要讲的内容。

归并排序的原理

我们先来看归并排序(Merge Sort)。
归并排序的核心思想还是蛮简单的。如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。
归并排序使用的就是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。
从我刚才的描述,你有没有感觉到,分治思想跟我们前面讲的递归思想很像。是的,分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧这两者并不冲突。分治算法的思想我后面会有专门的一节来讲,现在不展开讨论,我们今天的重点还是排序算法。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(699)

  • 最新
  • 精选
  • 置顶
    每次从各个文件中取一条数据,在内存中根据数据时间戳构建一个最小堆,然后每次把最小值给写入新文件,同时将最小值来自的那个文件再出来一个数据,加入到最小堆中。这个空间复杂度为常数,但没能很好利用1g内存,而且磁盘单个读取比较慢,所以考虑每次读取一批数据,没了再从磁盘中取,时间复杂度还是一样O(n)。
    12
    325
  • Light Lin
    伪代码反而看得费劲,可能还是对代码不够敏感吧

    作者回复: 那我以后还是写代码吧

    23
    572
  • 李建辉
    先构建十条io流,分别指向十个文件,每条io流读取对应文件的第一条数据,然后比较时间戳,选择出时间戳最小的那条数据,将其写入一个新的文件,然后指向该时间戳的io流读取下一行数据,然后继续刚才的操作,比较选出最小的时间戳数据,写入新文件,io流读取下一行数据,以此类推,完成文件的合并, 这种处理方式,日志文件有n个数据就要比较n次,每次比较选出一条数据来写入,时间复杂度是O(n),空间复杂度是O(1),几乎不占用内存,这是我想出的认为最好的操作了,希望老师指出最佳的做法!!!

    作者回复: 你回答的不错 思路是正确的

    58
    504
  • sherry
    还是觉得伪代码更好,理解思路然后可以写成自己写练练手,看完代码后就没啥想写的欲望了。

    作者回复: 真是众口难调啊😢

    8
    81
  • 大汉
    我是一个笨的人,一节课要看很多遍,但是我知道,只要比聪明的人多看几遍,就也会达到同样的效果

    作者回复: 👍,加油💪

    9
    63
  • 斗米担米
    当 T(n/2^k)=T(1) 时,也就是 n/2^k=1 这个为什么会等于T(1)啊

    作者回复: 最后数据区间变成1的时候排序就完成了 我们看n经过了多少次分解会变成1

    3
    42
  • angel😇txy🤓
    大家都说快排的伪代码不好理解,我用JAVA翻译了一下,实测通过,老师给个置顶哈。private static void quickSortC(int[] a, int p, int r) { if (p >= r) { return; } int q = partition(a, p, r); quickSortC(a, p, q - 1); quickSortC(a, q + 1, r); } public static int partition(int[] a, int start, int end) { int pivot = a[end]; int i = start; for (int j = start; j < end; j++) { if (a[j] < pivot) { swap(a, i, j); i = i + 1; } } swap(a, i, end); return i; }

    作者回复: 👍

    5
    26
  • 刘远通
    老师 这个地方我没看懂... “第一次分区查找,我们需要对大小为 n 的数组执行分区操作,需要遍历 n 个元素。第二次分区查找,我们只需要对大小为 n/2 的数组执行分区操作,需要遍历 n/2 个元素。依次类推,分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为 1。” 这里讨论的是最平均的情况吗? 最坏的情况可以n,n-1,...,1啊

    作者回复: 平均。你说的没错。最坏情况是你说的那样

    17
  • xr
    你可能会说,我有个很笨的办法,每次取数组中的最小值,将其移动到数组的最前面,然后在剩下的数组中继续找最小值,以此类推,执行 K 次,找到的数据不就是第 K 大元素了吗? 应该是每次取数组中的最“大”值放到前面吧,因为找的是第k大元素?

    作者回复: 嗯嗯 感谢指出

    3
    13
  • Mr.Panda
    自己本地实现归并排序后,觉得归并排序终止条件p==r就可以了,没必要大于等于,因为p只存在小于等于r的情况,请作者指导下,我是不是哪里没考虑到?

    作者回复: 貌似是的

    3
    5
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部