笔记之基于快排求解第k大问题

基于快排求解第k大问题时遇到的问题,记录之。

快排的思路

快排是常用的排序算法之一,很多编程语言都有内置的库函数实现。其思路就是:

  1. 在数组中找一个数A,将比A大的数全部移到A的左侧,比A小的数全部移到A的右侧;
  2. 然后各自在左侧和右侧的区间使用步骤1,直至左右侧的区间长度为1;

此外,快排的算法实现还会要求不占用额外的内存空间并且是稳定的排序。

很显然,就上述快排的思路而言,一般人在编程实现时大多会用到递归(注意:库函数 qsort 的实现并没有用到递归!)。递归是一种常用的编程技巧,它的思路就是找到一个递归公式,将当前问题转化成子问题进行求解。其一般的编程步骤,如:

// 递归终止条件

// 处理当前层

// 处理子问题:这里显式调用当前函数

// 收尾-非必需

为了便于理解,举段伪代码:

quick_sort_p(Array, p, q)
   //
   if p > q return
   //
   r = partition(Array, p, q)
   //
   quick_sort_p(Array, p, r - 1)
   quick_sort_p(Array, r + 1, q)

这里的分区函数 partition 很关键,它的实现决定了快排算法的效率和稳定性(原地排序)。假如每次以最后一个元素作为分区点,举一稳定的分区函数例子:

partion(Array, p, r)
   pivotTh := r
   pivot := Array[pivotTh]
   i := p
   for j := p to r - 1 do {
      if Array[j] < pivot {
         swap(Array, i, j)
         i := i + 1
      }
   }
   swap(Array, i, r)
   return i

第k大的数

第k大数问题的求解,如果使用上述快排的思路来求解的话,就是每次根据分区点 r 的大小(从大到小)进行递归:

  • r == k: r所对应的元素即是答案;
  • r > k: 对[p, r - 1]操作;
  • r < k: 对[r + 1, q]操作;

215 题

Leetcode 215 题可以使用上述算法来实现。很意外的是,即使每次分区点固定选择区间的最后一个元素,提交后并没有显示“超出时间限制”的错误。 添加分区点的“优化”:每次在分区区间内随机选择一位作为分区点,然后进行提交后,所得优化不多。私以为,此类题更适合堆排序。

1985 题

Leetcode 215 题是变种,给出的数组元素是由数字组成的字符串。 于是,比较两个元素大小的时候要从两个维度考虑:长度相同的,使用 strcmp,否则长度大的元素大。如果使用215题的思路求解的时候,即使添加随机选择分区点的“优化”,提交后也会遇到“超出时间限制”的错误。失败的测试用例输入形如:

["9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999","9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", 1,1,...] //10000个元素
10000

但很奇怪,单次执行该输入用例又能通过。对于这种退化到求最小值( k == size - 1)的情形,单独处理后,提交能通过。但是时间大概需要600ms,已经不能够在执行用时分布图上显示了。于是改用库函数 qsort 并提交,用时大概 128ms——虽然知道库函数必定是有优化的,但这一下子引起了我的兴趣。

qsort 源码

于是,搜索并看了下 glibc 中的qsort 实现,我没有完全看懂 :-(。不过可以在网上搜到他人的解读,大家可以自行搜索。 我看完源码的感受就是:

  • 使用宏实现了一个高效的元素交换;
  • 实现了一个巨快的内连的栈;
  • 实现了 Sedgewick 阐明的4个优化;

其中4个优化指的是:

  1. 非递归的算法:使用栈;
  2. 使用三数中位数的决策树来获取分区点;
  3. 只对 数组长度/4 区间进行分区(4是经过研究发现的魔法数),每个区间使用插入算法排序;
  4. 上述分区最大的两个先入栈,这样让算法先作用于长度小的分区;

参考资料

算法通关面试40讲
qsort.c
Engineering a Sort Function
glibc的qsort迭代实现源码