kdb - Q/KDB+ 中的快速排序

Question

我在一个网站上找到了这个快速排序实现：

q:{$[2>distinct x;x;raze q each x where each not scan x < rand x]};

我不明白这部分：

raze q each x where each not scan x < rand x

有人可以逐步向我解释吗？

Answer 1

让我们一步一步来。我假设您对快速排序算法有基本的了解。此外，您提到的代码中有一处更正，我已在步骤 5 中进行了更正。

示例列表：

                q)x: 1 0 5 4 3

1. 从列表中获取一个随机元素，该元素将充当枢轴。

      q)  rand x
   

   假设它给了我们列表中的“4”。

2. 在 2 个列表中拆分列表“x”。一个包含小于“4”的元素，另一个包含大于（或等于）“4”的元素。

   2.a）首先将所有元素与枢轴（在我们的例子中为4）进行比较

                 q)   (x<rand x)   /  11001b  : output is boolean list 
   

   2.b）使用上面的布尔列表，我们可以从“x”中获取小于“4”的所有元素。这是方法：

        q) x where  11001b  / ( 1  0 3) : output
   

   因此，我们需要其他表达式来获取大于（或等于）枢轴“4”的所有元素。有很多方法可以做到这一点，但让我们看看代码中使用的一种：

         q)not scan (x<rand x)   / (11001b;00110b) : output
   

所以它给出了有 2 个列表的列表。首先是 (x < rand x) 的结果，它用于获取小于枢轴“4”的元素，另一个是该列表的否定，由“not”完成，它用于获取大于（或等于）的所有元素枢轴'4'。

2.c) 所以现在我们可以使用 (2.b) 中的示例代码生成 2 个列表

       q) x where each (not scan (x<rand x)) / ((1 0 3);(5 4)): output list which has 2 lists

3. 现在对每个列表应用相同的函数来对它们中的每一个进行排序，即对每个列表列表进行递归调用 ((1 0 3);(5 4))

       q) q each x where each (not scan (x<rand x))
   

   4. 在所有计算之后，应用“raze”来展平从每个递归调用返回的所有列表，以输出一个列表。

   5. 递归调用的结束条件是：当输入列表只有 1 个不同的元素时，只需返回它。

         q) 2>count distinct x
      

      注：有一处更正。原始代码中缺少“计数”。