延迟排序

wiki

基本的快速排序算法如下所示

To quicksort(Set)
  If Set is empty, then return an empty vector
  Otherwise
    Select a value in Set, Pivot
    Make Left from all values in Set less than Pivot
    Make Right from all values in Set greater than Pivot
    Return the concatenation of Quicksort(Left), Pivot, Quicksort(Right)

如果将最后一步的连接替换为创建二叉树节点，则二叉树会变得非常明显。然后可以通过展平二叉树来创建最终的向量。

类似地，我们可以通过首先创建一个从 1 到 n 的整数向量，然后将向量中的元素相乘来计算阶乘(n)。

在这两种情况下，我们都有一种“虚拟”中间结构，实际上我们通过将其合并到程序流程中来消除它。[1] 但是，有时揭示中间结构可能很有用。

例如，假设我们有一个非常大的家庭收入向量，比如一百万个家庭。我们想要计算收入不平等的某种度量；一个常见的度量是找到最高五分位数（即收入最高的 20% 人口）的平均收入与最低五分位数（即收入最低的 20% 人口）的平均收入之间的比率。

为了计算这个值，我们需要对收入向量进行半排序。理想情况下，我们希望只对它进行足够的排序，以便我们可以提取（无序的）第一个和最后一个五分位数。一种通用的方法是延迟运行快速排序算法；首先，我们在到达对应于 20% 点的节点时停止；然后我们重新开始，在到达 80% 点时停止。为了做到这一点（一般来说），我们需要保留至少一部分隐式二叉树。

一种方法是改变快速排序，使递归被“承诺”替换；也就是说，我们不是真正地进行递归，而是创建一个函数闭包，当调用它时，它将执行下一步递归。

Lua 发行版包含 sort.lua，它包含一个简单的快速排序实现；略微简化后，核心如下所示

function qsort(vec, low, high)
  if low < high then
    local middle = partition(vec, low, high)
    qsort(vec, low, middle-1)
    qsort(vec, middle+1, high)
  end
end

我已经将 partition 函数分离出来，并为变量赋予了可能更有意义的名称，以使算法更清晰。

延迟版本看起来像这样

-- Ensure that that the element at i is in the right position,
-- and return a closure which can be used for continuing the sort.
function quicksorter(i, vec, low, high)
  if low >= high then
    return quicksorter
  else -- low < high
    -- partition the vector and initialize the child closures
    local middle = partition(vec, low, high)
    local left, right = quicksorter

    -- Create the promise
    local function self(i, vec, low, high)
      if i < middle then
        left = left(i, vec, low, middle-1)
        return self
      elseif i > middle then
        right = right(i, vec, middle+1, high)
        return self
      end
    end
    
    -- Force the promise until i is in the right position
    return self(i, vec, low, high)
  end
end

function lazysort(vec, low, high)
  local sorter = quicksorter
  return function(i)
    sorter = sorter(i, vec, low, high)
    return vec[i]
  end
end

我还没有实际测试上面的代码，但我确实编写了一个真实的 lazysort 版本；你可以从 [这里] 下载它。真实版本包含几个效率：首先，它对小范围使用插入排序；其次，它合并二叉树，使其始终完整。

示例代码包含一个测试套件和基准测试，以及一些被注释掉的代码，这些代码可以使我们能够通过使用哨兵索引值递归遍历闭包来查看“虚拟”二叉树。我用它来制作以下关于它如何工作的插图

首先，让我们测试一下

function rangemean(v, low, high)
  local sum = v[low]
  for i = low+1, high do sum = sum + v[i] end
  return sum / (high - low + 1)
end

function disparity(v)
  local getter = lazysort(v)
  local bottom = math.ceil(#v / 5)
  getter(bottom)
  local top = math.floor(#v * 4 / 5)
  getter(top)
  return rangemean(v, top, #v) / rangemean(v, 1, bottom)
end

> math.randomseed(31415926)
> test = {}; for i = 1, 1e6 do test[i] = math.random(1e4) end
> now = os.clock(); print(disparity(test)); print(os.clock() - now)
8.9768793870336
0.6796875
>
> -- By comparison:
>
> math.randomseed(31415926)
> test = {}; for i = 1, 1e6 do test[i] = math.random(1e4) end
> now = os.clock(); table.sort(test); print (rangemean(test,8e5,1e6)/rangemean(test,1,2e5)); print(os.clock() - now)
8.9768793870336
1.8828125

所以即使它用 Lua 编写，table.sort 用 C 编写，它对于这种计算来说速度快了三倍。换句话说，它不是玩具。

以下是它的工作原理。让我们取一个稍微小的样本

> test = {}; for i = 1, 500 do test[i] = math.random(1e4) end
> getter = lazysort(test)
> =getter(100)
1954
>
> -- By uncommenting the viewing code, we can look at the tree structure:
> getter""
Root
+-Sorted [1, 1)
+-Node [1, 501)
| +-Node [1, 249)
| | +-Node [1, 169)
| | | +-Leaf [1, 47) Unsorted
| | | +-Sorted [47, 48)
| | | +-Node [48, 169)
| | |   +-Leaf [48, 83) Unsorted
| | |   +-Sorted [83, 103)
| | |   +-Leaf [103, 169) Unsorted
| | +-Sorted [169, 170)
| | +-Leaf [170, 249) Unsorted
| +-Sorted [249, 250)
| +-Leaf [250, 501) Unsorted
+-Sorted [501, 500)
> 
> -- "Partitioned" would be a better word than "Unsorted". 
> -- Now, let's ask for another element, some distance away
>
> =getter(400)
7877
> getter""
Root
+-Sorted [1, 1)
+-Node [1, 501)
| +-Node [1, 249)
| | +-Node [1, 169)
| | | +-Leaf [1, 47) Unsorted
| | | +-Sorted [47, 48)
| | | +-Node [48, 169)
| | |   +-Leaf [48, 83) Unsorted
| | |   +-Sorted [83, 103)
| | |   +-Leaf [103, 169) Unsorted
| | +-Sorted [169, 170)
| | +-Leaf [170, 249) Unsorted
| +-Sorted [249, 250)
| +-Node [250, 501)
|   +-Leaf [250, 382) Unsorted
|   +-Sorted [382, 383)
|   +-Node [383, 501)
|     +-Node [383, 441)
|     | +-Leaf [383, 391) Unsorted
|     | +-Sorted [391, 408)
|     | +-Leaf [408, 441) Unsorted
|     +-Sorted [441, 442)
|     +-Leaf [442, 501) Unsorted
+-Sorted [501, 500)
>
> -- Leaf [250, 501) has now been expanded down to element 400.
>
> -- Now, let's watch as it merges tree nodes.
>
> =getter(387)
7546
> getter""
Root
+-Sorted [1, 1)
+-Node [1, 501)
| +-Node [1, 249)
| | +-Node [1, 169)
| | | +-Leaf [1, 47) Unsorted
| | | +-Sorted [47, 48)
| | | +-Node [48, 169)
| | |   +-Leaf [48, 83) Unsorted
| | |   +-Sorted [83, 103)
| | |   +-Leaf [103, 169) Unsorted
| | +-Sorted [169, 170)
| | +-Leaf [170, 249) Unsorted
| +-Sorted [249, 250)
| +-Node [250, 501)
|   +-Leaf [250, 382) Unsorted
|   +-Sorted [382, 408)
|   +-Node [408, 501)
|     +-Leaf [408, 441) Unsorted
|     +-Sorted [441, 442)
|     +-Leaf [442, 501) Unsorted
+-Sorted [501, 500)
>
> Leaf [383, 391] has been fully sorted, so it can be merged into it's parent, Node [383, 441).
> That in turn creates another merge, leaving the tree as shown above. 

[1] 对于稍微更学术（但仍然可以理解）的讨论，请阅读 Lex Augusteijn 关于 [排序态射] 的有趣论文。