笔记之基于快排求解第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迭代实现源码

Comments

Categories

Tags