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

精选留言(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