JavaScript 中的 Haskell 快速排序

Haskell 对快速排序算法有一个特别优雅的实现：

qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) =
  let smaller = qs [a | a <- xs, a <= x]
      bigger = qs [a | a <- xs, a > x]
  in  smaller ++ [x] ++ bigger

该算法创建一个新的已排序数组，而不是对给定数组进行原地排序。因此，实现分区策略（通常是霍尔策略）毫无意义。

对于不熟悉 Haskell 的人来说，这可能看起来像一堆废话。让我们分解一下，看看如何在 JavaScript 中写出一个优雅的版本。

类型签名

qs :: (Ord a) => [a] -> [a]

这只是一个类型签名，可以这样理解：“qs是一个函数，它接受一个数组as并生成一个新的数组，其中as每个元素都a可以与另一个元素进行比较。” 这(Ord a)部分是一个类型约束，意味着as需要具有可比性，这是有道理的，因为这是一个排序算法。

模式匹配

qs [] = []
qs (x:xs) = -- and so on...

模式匹配有点像函数重载和解构的结合。JavaScript 没有函数重载，但有解构。我们可以(x:xs)像[x, ...xs]在 JavaScript 中那样写。可惜的是，我们必须手动检查数组是否为空。

Let 表达式

let smaller = qs [a | a <- xs, a <= x]
    bigger = qs [a | a <- xs, a > x]
in  smaller ++ [x] ++ bigger

在 Haskell 中，一切都是表达式，而不是语句。表达式是产生值的东西。语句只是执行某些操作的代码行。有时，在表达式中定义中间值很有用，这就是 let 块的作用。该块的结果是一个数组smaller ++ [x] ++ bigger。

列表推导

[a | a <- xs, a <= x]

列表推导式使用生成器和保护（或过滤器）生成列表（或数组）。这段代码可以理解为“给我一个列表，as其中 eacha是从列表中取出的xs，并且小于或等于x。”（这实际上只是在 do 符号之上添加的语法糖，而 do 符号本身只是单子组合的语法糖，但这是另一个话题了。）

不幸的是，JavaScript 没有列表推导，所以我们能做的最好的就是使用Array.filter方法：xs.filter(s => s <= x)。箭头函数提供了一种相对优雅的替代方案。

现在使用 JavaScript

这里有个巧妙的技巧：由于只有两个逻辑分支，三元运算符提供了一种很好的处理条件的机制。我们可以使用解构将数组拆分为头部和尾部。然后，如果头部未定义（因为数组为空），则使用三元运算符返回一个空数组；否则，返回一个由较小数组、当前元素和较大数组组成的新数组。最终代码如下：

const qs = ([x, ...xs]) => x === undefined 
  ? [] 
  : [
    ...qs(xs.filter(s => s <= x)),
    x,
    ...qs(xs.filter(b => b > x))
  ]

这个实现最酷的地方在于，它只是一个表达式！根本没有任何变量声明（除了快速排序算法本身被赋值给一个常量）。

这当然不是快速排序算法最高效的实现，但它演示了如何利用 JavaScript 的特性编写优雅的代码。如果 JavaScript 中能有模式匹配、列表推导和 let 表达式就更好了，但 JavaScript 现有的工具也能让你走得更远。在一个代码清晰度和可维护性日益重要、设备容量几乎被过度利用的行业中，编写正确、清晰、简洁的代码的能力至关重要。

编辑：

Amn3s1a2018 指出，我的原始代码没有明确检查x === undefined包含零的数组，因此会失败。

Amn3s1a2018 • 21年10月21日

这是一个很酷的重构示例，也是一个常见错误的示例...
三元运算符很好地替代了重载，但正确的方法是

惊喜，惊喜

x !== 未定义 ? 等。

因为这样 qs 就会从数组中过滤掉所有虚假元素，并且也会丢弃它们的尾部。

如前所述，这不是 JavaScript 中最高效的排序方法，我不建议在实际生产中使用它。如果你想要一个高效的排序算法，并返回一个新的数组，请使用以下命令：

const qs = (arr) => [...arr].sort((a, b) => a - b);