数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

归并排序的原理

我们先来看归并排序(Merge Sort)。
归并排序的核心思想还是蛮简单的。如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。
归并排序使用的就是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。
从我刚才的描述,你有没有感觉到,分治思想跟我们前面讲的递归思想很像。是的,分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突。分治算法的思想我后面会有专门的一节来讲,现在不展开讨论,我们今天的重点还是排序算法。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(411)

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

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

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

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

    2018-10-28
    14
    205
  • 你有资格吗?
    建议还是写源码吧,伪代码不能体现细节,基础不好的同学看起来也费劲,还有一个问题课后思考能不能在下一节课开头讲一下,因为感觉您每次留的课后思考都很精辟,想知道以您的维度怎么来思考和解决这个问题
    2018-10-18
    1
    187
  • 王先统
    可以为每个文件分配一个40M的数组,再另外分配一个400M的数组储存归并结果,每个文件每次读取40M,对十个数组做归并排序直到其中某个数组的数据被处理完,这时将归并结果写入磁盘,处理完的数组继续读入40M继续参与归并,以此类推,直到所有文件都处理完
    2018-10-17
    5
    77
  • 侯金彪
    老师,有个问题没懂,在一个数组中找第k大的数这个问题中,为什么如果p+1=k,a[p]就是要查找的结果呢?
    2018-10-17
    13
    47
  • 我来也
    我觉得最后的思考题,[曹源]同学的策略是较优的。
    该策略的最大好处是充分利用了内存。
    但是我还是会这么做:
    1.申请10个40M的数组和一个400M的数组。
    2.每个文件都读40M,取各数组中最大时间戳中的最小值。
    3.然后利用二分查找,在其他数组中快速定位到小于/等于该时间戳的位置,并做标记。
    4.再把各数组中标记位置之前的数据全部放在申请的400M内存中,
    5.在原来的40M数组中清除已参加排序的数据。[可优化成不挪动数据,只是用两个索引标记有效数据的起始和截止位置]
    6.对400M内存中的有效数据[没装满]做快排。
    将排好序的直接写文件。
    7.再把每个数组尽量填充满。从第2步开始继续,知道各个文件都读区完毕。
    这么做的好处有:
    1.每个文件的内容只读区一次,且是批量读区。比每次只取一条快得多。
    2.充分利用了读区到内存中的数据。曹源 同学在文件中查找那个中间数是会比较困难的。
    3.每个拷贝到400M大数组中参加快排的数据都被写到了文件中,这样每个数只参加了一次快排。
    2018-10-21
    13
    46
  • www.xnsms.com小鸟接码
    用java来写吧,估计这里90%都是java开发!伪代码看的蛋疼
    2018-10-23
    17
    44
  • 周茜(Diane)
    看了十几节课,第一次留言竟然是支持老师写伪代码。捂脸。不希望被代表。另外希望总结的同学,尽量少写一点吧,翻着太累了。我也写总结,在自己的笔记应用里。默写。写完再查漏补缺。感觉效果很好,也能检查自己到底学进去多少。
    2018-10-26
    33
  • 曹源
    先取得十个文件时间戳的最小值数组的最小值a,和最大值数组的最大值b。然后取mid=(a+b)/2,然后把每个文件按照mid分割,取所有前面部分之和,如果小于1g就可以读入内存快排生成中间文件,否则继续取时间戳的中间值分割文件,直到区间内文件之和小于1g。同理对所有区间都做同样处理。最终把生成的中间文件按照分割的时间区间的次序直接连起来即可。
    2018-10-18
    1
    33
  • sherry
    还是觉得伪代码更好,理解思路然后可以写成自己写练练手,看完代码后就没啥想写的欲望了。

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

    2018-10-21
    3
    31
  • 陈华应
    坚持初衷,死磕就行,不退缩,不放弃!
    2018-10-17
    27
  • Lx
    合并函数借助哨兵简化方法
    传入的后两个数组各在尾部多放一个和原有最后值相同的值。
    循环改为:
    while i<=q or j<=r do{
        if A[i] <= A[j] and i<=q {
            tmp[k++] = A[i++]
        }
        else{
            tmp[k++] = A[j++]
        }
    }
    可以在while循环里完成两个数组的清空,不需要专用部分完成。
    2018-10-23
    8
    25
  • The Sword of Damocles
    王道考研书上看到的快排算法,利用哨兵减少了交换两个元素的复杂步骤,效果更好一些
    private static void quickSort(int[] a, int head, int tail) {

            int low = head;
            int high = tail;
            int pivot = a[low];
            if (low < high) {

                while (low<high) {
                    while (low < high && pivot <= a[high]) high--;
                    a[low] = a[high];
                    while (low < high && pivot >= a[low]) low++;
                    a[high]=a[low];
                }
                a[low] = pivot;

                if(low>head+1) quickSort(a,head,low-1);
                if(high<tail-1) quickSort(a,high+1,tail);
            }

        }
    2018-11-01
    5
    22
  • 姜威
    三、快速排序
    1.算法原理
    快排的思想是这样的:如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot(分区点)。然后遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将povit放到中间。经过这一步之后,数组p到r之间的数据就分成了3部分,前面p到q-1之间都是小于povit的,中间是povit,后面的q+1到r之间是大于povit的。根据分治、递归的处理思想,我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据,直到区间缩小为1,就说明所有的数据都有序了。
    递推公式:quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
    终止条件:p >= r
    2.代码实现(参见下一条留言)
    3.性能分析
    1)算法稳定性:
    因为分区过程中涉及交换操作,如果数组中有两个8,其中一个是pivot,经过分区处理后,后面的8就有可能放到了另一个8的前面,先后顺序就颠倒了,所以快速排序是不稳定的排序算法。比如数组[1,2,3,9,8,11,8],取后面的8作为pivot,那么分区后就会将后面的8与9进行交换。
    2)时间复杂度:最好、最坏、平均情况
    快排也是用递归实现的,所以时间复杂度也可以用递推公式表示。
    如果每次分区操作都能正好把数组分成大小接近相等的两个小区间,那快排的时间复杂度递推求解公式跟归并的相同。
    T(1) = C; n=1 时,只需要常量级的执行时间,所以表示为 C。
    T(n) = 2*T(n/2) + n; n>1
    所以,快排的时间复杂度也是O(nlogn)。
    如果数组中的元素原来已经有序了,比如1,3,5,6,8,若每次选择最后一个元素作为pivot,那每次分区得到的两个区间都是不均等的,需要进行大约n次的分区,才能完成整个快排过程,而每次分区我们平均要扫描大约n/2个元素,这种情况下,快排的时间复杂度就是O(n^2)。
    前面两种情况,一个是分区及其均衡,一个是分区极不均衡,它们分别对应了快排的最好情况时间复杂度和最坏情况时间复杂度。那快排的平均时间复杂度是多少呢?T(n)大部分情况下是O(nlogn),只有在极端情况下才是退化到O(n^2),而且我们也有很多方法将这个概率降低。
    3)空间复杂度:快排是一种原地排序算法,空间复杂度是O(1)
    四、归并排序与快速排序的区别
    归并和快排用的都是分治思想,递推公式和递归代码也非常相似,那它们的区别在哪里呢?
    1.归并排序,是先递归调用,再进行合并,合并的时候进行数据的交换。所以它是自下而上的排序方式。何为自下而上?就是先解决子问题,再解决父问题。
    2.快速排序,是先分区,在递归调用,分区的时候进行数据的交换。所以它是自上而下的排序方式。何为自上而下?就是先解决父问题,再解决子问题。
    五、思考
    1.O(n)时间复杂度内求无序数组中第K大元素,比如4,2,5,12,3这样一组数据,第3大元素是4。
    我们选择数组区间A[0...n-1]的最后一个元素作为pivot,对数组A[0...n-1]进行原地分区,这样数组就分成了3部分,A[0...p-1]、A[p]、A[p+1...n-1]。
    如果如果p+1=K,那A[p]就是要求解的元素;如果K>p+1,说明第K大元素出现在A[p+1...n-1]区间,我们按照上面的思路递归地在A[p+1...n-1]这个区间查找。同理,如果K<p+1,那我们就在A[0...p-1]区间查找。
    时间复杂度分析?
    第一次分区查找,我们需要对大小为n的数组进行分区操作,需要遍历n个元素。第二次分区查找,我们需要对大小为n/2的数组执行分区操作,需要遍历n/2个元素。依次类推,分区遍历元素的个数分别为n、n/2、n/4、n/8、n/16......直到区间缩小为1。如果把每次分区遍历的元素个数累加起来,就是等比数列求和,结果为2n-1。所以,上述解决问题的思路为O(n)。
    2.有10个访问日志文件,每个日志文件大小约为300MB,每个文件里的日志都是按照时间戳从小到大排序的。现在需要将这10个较小的日志文件合并为1个日志文件,合并之后的日志仍然按照时间戳从小到大排列。如果处理上述任务的机器内存只有1GB,你有什么好的解决思路能快速地将这10个日志文件合并?
    2018-10-22
    19
  • MARK
    懵逼了,智商欠费,今天晚上死磕这篇了
    2018-10-19
    19
  • 见贤思齐
    我测试出,伪代码中
    '
    partition(A, p, r) {
      pivot := A[r]
      i := p
      for j := p to r-1 do {
        if A[j] < pivot {
          swap A[i] with A[j]
          i := i+1
        }
      }
      swap A[i] with A[r]
      return i
    '

    ' for j := p to r-1 do '

    中的 r-1 应该是 r
    2018-10-19
    5
    17
  • oldman
    我用python实现了归并排序和快速排序,代码如下:
    归并排序:https://github.com/lipeng1991/testdemo/blob/master/45_merge_sort.py
    快速排序: https://github.com/lipeng1991/testdemo/blob/master/23_quick_sort.py
    欢迎一起探讨。今天又回想了一下上一节的三个排序和今天的两个排序,自己又动手画了一下图,实现了一下代码,确切来讲,要想很深的掌握这些东西是需要不断的回想,不断的训练来加深印象的,想想以前学习算法为什么会感觉那么的难,其实就是练的不够,不要太着急的一下子把所有的算法都实现一遍,温故而知新,跟着老师的这个专栏来,一点一点的啃,啃着现在的复习前面的,你会越来越有成就感,你会越来越自信,这就是建立在不断的训练的基础上的。
    2018-10-22
    16
  • adrian-jser
    看到好多同学说建议不要为代码的。
    我觉得专栏文章就是教你分析问题和解决问题的思路,具体的代码不是有作者贴出的github地址吗
    2018-11-26
    1
    14
  • 斗米担米
    当 T(n/2^k)=T(1) 时,也就是 n/2^k=1
    这个为什么会等于T(1)啊

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

    2018-11-05
    14
收起评论
99+
返回
顶部