Q/KDB+ 中的快速排序

Quicksort in Q/KDB+

kdb
q-lang

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

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

谁能一步步给我解释一下？

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

示例列表：

                q)x: 1 0 5 4 3

从列表中随机取一个元素作为基准。
```
   q)  rand x
```
假设它给我们列表中的“4”。
拆分列表 'x' 为 2 个列表。一个包含小于“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) 的结果，它用于获取小于 pivot '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

现在对每个列表应用相同的函数来对每个列表进行排序即递归调用列表的每个列表 ((1 0 3);(5 4))
```
    q) q each x where each (not scan (x<rand x))
```
1. 在所有计算之后，应用 'raze' 来展平所有从每个递归调用中 return 编辑的列表，以输出一个列表。
2. 递归调用的结束条件是：当输入列表只有 1 个不同的元素时 return 它。
```
   q) 2>count distinct x
```
  注：有一处更正。原始代码中缺少 'count'。