C# 和 F# 中的快速字符串排序
4.97/5 (43投票s)
多键字符串快速排序的实现（遵循 Sedgewick）。
引言
.NET 中的通用排序算法在字符串排序方面的性能不佳。原因在于它在比较字符串时执行了过多的字符比较。
Robert Sedgewick 教授描述了一种更好的算法，称为多键快速排序。Sedgewick 因其面向开发人员的算法书籍及其对算法性能进行经验研究的方法而闻名。在字符串排序的情况下，Sedgewick 提供了 C 语言的字符串排序参考实现。
他的实现理解起来相当困难，但实现了卓越的性能。
C# 和 F# 中的字符串排序实现
我提供了多键快速排序算法的三种 C# 和 F# 实现（除了下面的伪代码）。我的实现与 Sedgewick 的略有不同，速度也略慢，但比 .NET 实现快得多。最初，我很难适应 Sedgewick 的实现，因为字符串可能包含“\0”字符的边缘情况。在新代码中，此问题已修复，我提供了非常接近参考的 C# 实现。
.NET 排序的问题不在于实现本身，而在于算法。.NET 实现了普通快速排序，这是整数或双精度浮点数最快的算法之一。Sedgewick 提出了对普通快速排序的一些扩展，这些扩展使该算法适用于
- 包含重复数据
- 多键数据，例如字符串或字符数组
此外，Sedgewick 还使用了另外两个技巧
- 小数组的插入排序
- 9 个伪中位数以找到一个好的枢轴
多键快速排序的伪代码
字符串排序的真实代码有些难以理解，因为它使用了就地更新和多个索引。然而，多键快速排序算法却并非如此。在本节中，我将提供实际的 F# 代码作为伪代码。此代码可以作为实际算法的高级规范。但是，此伪代码省略了影响性能的细节。
let filter = Array.filter //used as an alias //line 1
let concatenate = Array.concat //another alias //line 2
let cmp (depth: int, s: string, t: string) = //line 3
let lenS, lenT = s.Length, t.Length
assert(lenS >= depth); assert(lenT >= depth) //line 4
if (lenS = depth && lenT = depth) then (*return*) 0 //line 5
else if (lenS = depth) then (*return*) -1 //line 6
else if (lenT = depth) then (*return*) 1 //line 7
else
assert(lenS > depth); assert(lenT > depth) //line 8
let chS, chT = s.[depth], t.[depth] //line 9
if chS < chT then (*return*) -1 //line 10
else if chS = chT then (*return*) 0 //line 11
else (*return*) 1 //line 12
// Do not use in production. This code is meant to serve as pseudo-code only
// Production code uses details that are not presented here
let rec pseudoCodeMultiKeyQuickSort(input: string[], depth: int): string[] = //line 13
if (input.Length = 0) then Array.empty //line 14
else
let pivot = input.[input.Length / 2] //in reality median of 3 or 9 is used //line 15
//in reality the following filters are done in place in two passes //line 16
let less = filter(fun s -> cmp(depth, s, pivot) < 0) input // s < pivot //line 17
let eq = filter(fun s -> cmp(depth, s, pivot) = 0) input // s = pivot //line 18
let gt = filter(fun s -> cmp(depth, s, pivot) > 0) input // s > pivot //line 19
let sortedLess = pseudoCodeMultiKeyQuickSort(less, depth) //line 20
let sortedEq = if (eq.Length > 0 && depth < eq.[0].Length) then //line 21
pseudoCodeMultiKeyQuickSort
(eq, depth + 1) //note that depth grows //line 21
else eq //line 22
let sortedGt = pseudoCodeMultiKeyQuickSort(gt, depth) //line 23
//in reality the algorithm updates the same array and
//recursively passes from and to indices to define subarrays
(*return*)
concatenate [|sortedLess; sortedEq; sortedGt|] //line 24
let pseudoStringSort (input: string[]) = //line 25
(*return*) pseudoCodeMultiKeyQuickSort(input, 0 (*depth*)) //line 26
pseudoStringSort [|"aaa";"a";"b";"";"ba";"bbb"|]
请注意比较函数（名为 `cmp`，第 3 行），它除了要比较的两个字符串 (`s` 和 `t`) 之外，还带有一个深度参数。另请注意算法如何在两个维度上递归：子数组和深度参数（参见图 1）。您可以认为该算法在层级上操作：首先按第一个字符排序，找到所有第一个字符等于枢轴的字符串，并且仅针对这组字符串，按第二个字符排序。随着深度参数的增长，必须特别注意字符用尽的字符串。深度仅在第 21 行增长。在该行中，我们有一块字符串，它们具有从 0 到深度（包括）的相同前缀。随着深度的增长，它最终将以空字符串结束。如果相等字符串块（第 21 行）中第一个字符串的当前后缀（从深度开始）是空字符串（通过 `eq.[0].Length` 条件测试），那么由于此块中的所有字符串都相等，它们都为空。这被用作深度递归的终止条件。另一个终止条件是子数组已变空。
最后，对于不熟悉 F# 的读者，一些关于 F# 语法的注释可能会有所帮助。`[|a;b;c|]` 用于表示由 `a`、`b` 和 `c` 组成的数组；`arr.[index]` 用于访问索引位置的元素；`let x = 2` 用于将变量 `x` 绑定到值 `2`；`fun s -> f(s)` 是 F# 中 lambda 表达式的语法，或者一个谓词，它将接受 `s` 并使用参数 `s` 运行 `f`，并将 `f` 的结果返回给调用者。谓词可能会执行多次。
判断字符串排序算法的维度
以下维度将影响哪种字符串排序算法表现最佳
输入长度
小数组与大数组。.NET Sort 在小型字符串数组和字符串较短的数组上表现良好。随着输入数组大小的增加，或数组中字符串的增加，.NET 将花费更长的时间才能终止。
重复字符串
如果存在大量重复字符串，多键快速排序（如 Sedgewick 为字符串实现的）中的三路分区（即分区为三部分）将弥补其开销。如果不预期重复字符串，二路分区算法将更快。三路分区以以下方式工作。选择一个枢轴，最后将元素分区为以下顺序的三个桶：“`<= 枢轴`”、“`= 枢轴`”和“`>= 枢轴`”。相比之下，二路分区将只使用两个桶：“`<= 枢轴`”和“`> 枢轴`”。三路分区在不使用额外数组的情况下实现更复杂，因为它首先将元素按给定顺序分为四组：“`= 枢轴`”、“`< 枢轴`”、“`> 枢轴`”、“`= 枢轴`”。然后将两个“`= 枢轴`”块移回中间：“`< 枢轴`”、“`= 枢轴`”、“`= 枢轴`”、“`> 枢轴`”。除了比二路快速排序具有更大的内循环外，三路快速排序的一次迭代需要更多的数据交换。内循环中的代码大小极大地影响快速排序的性能。但是，如果“`= 枢轴`”块恰好很大，那么在对“`< 枢轴`”和“`> 枢轴`”块进行快速排序递归时，需要做的工作就更少。在多键快速排序的情况下，枢轴是一个字符，很可能会匹配许多元素。
字符串长度
如果输入数组包含越来越大的字符串，字符串排序和通用排序之间的比率通常会变大。如果待排序的字符串包含大量长公共前缀，这种情况会更糟。英语语言中的单词排序就是这种情况。
对非英语语言的适应
提供的参考代码通过从第一个字符到最后一个字符比较字符串的字符，并根据它们的 ASCII 码比较字符来对字符串进行排序。存在两个问题：反向排序顺序和非英语语言。
- 首先，即使您提供一个按*反向*排序的字符比较器，除非算法改变，否则它也无法工作。这是由空字符串（或随着深度参数的增长而变为空的字符串）引起的。可以更改算法以适应反向比较器，但仅提供字符比较器是不够的。
- 第二个问题与以下事实有关：对于许多语言，字符比较器不足以派生字符串比较器。该问题在 MSDN 文章中有所概述，标题为
在某些地区设置中，字符和字母之间不存在一对一的对应关系。要在非英语语言中排序，应该将字符序列分解为字母，然后按字母排序。幸运的是，.NET 提供了一个名为 `SortKey` 的类，它将非英语语言中的字符串转换为字节数组。通过它们对应的字节数组对字符串进行排序将产生正确的排序顺序。通过这种方式，多键快速排序算法可以很容易地适应对字节数组而不是字符串进行操作。有关将字符串转换为 `SortKey` 的详细信息，请查阅引用的 MSDN 文章。出于效率目的，应在运行排序算法之前将字符串转换为 `SortKey`。
比较
如上一节所述，仔细比较排序算法将必须至少考虑上述输入维度。最好固定两个维度，并根据第三个维度的值绘制运行时间。由于时间有限，我将只显示三个维度都相对较大的运行时间。我的代码包含一个函数，该函数将运行并测试所有算法，用于指定维度的自动生成输入。此函数可在提供的 F# 文件中找到。
number of unique elements = 5000000;
number of duplicates for each unique element = 5;
length of each string = 20;
random seed = 384585;
================================================================
String Sort in C# : avg: 31.247667(sec.) 0.4 %
String Sort in F# : avg: 44.563966(sec.) 43.2 %
Sedgewick (translated to C#): avg: 31.119719(sec.) 0.0 %
Dot Net Generic Sort : avg: 145.528939(sec.) 367.6 %
Fixed parameters as above, variable string length
===============================================================
string length = 5
-------------------
String Sort in C# : avg: 25.546378(sec.) 1.1 %
String Sort in F# : avg: 33.159264(sec.) 31.2 %
Sedgewick (translated to C#): avg: 25.268513(sec.) 0.0 %
Dot Net Generic Sort : avg: 129.865247(sec.) 413.9 %
===============================================================
string length = 10
-------------------
String Sort in C# : avg: 29.166639(sec.) -6.5 %
String Sort in F# : avg: 46.012092(sec.) 47.4 %
Sedgewick (translated to C#): avg: 31.210900(sec.) 0.0 %
Dot Net Generic Sort : avg: 152.109868(sec.) 387.4 %
===============================================================
string length = 20
-------------------
String Sort in C# : avg: 37.304173(sec.) 16.2 %
String Sort in F# : avg: 52.745780(sec.) 64.3 %
Sedgewick (translated to C#): avg: 32.095941(sec.) 0.0 %
Dot Net Generic Sort : avg: 162.737198(sec.) 407.0 %
===============================================================
string length = 40
-------------------
String Sort in C# : avg: 39.446201(sec.) 9.1 %
String Sort in F# : avg: 52.786923(sec.) 46.0 %
Sedgewick (translated to C#): avg: 36.151525(sec.) 0.0 %
Dot Net Generic Sort : avg: 167.100856(sec.) 362.2 %
===============================================================
string length = 40
-------------------
String Sort in C# : avg: 44.527835(sec.) 26.9 %
String Sort in F# : avg: 54.424359(sec.) 55.1 %
Sedgewick (translated to C#): avg: 35.098257(sec.) 0.0 %
Dot Net Generic Sort : avg: 164.124873(sec.) 367.6 %