以 O(N) 时间对可变长度字符串进行排序

• 下载源代码 - 126.3 KB

引言

本文所述算法旨在实现 O(n) 时间内对可变长度字符串进行排序。该实现对输入字符串文件进行排序。在处理输入文件时，此程序使用两个链表，一个用于存储字符串，另一个用于存储字符串的属性。与静态或堆动态数组相比，这使得处理可变长度字符串的实现更加优雅。文件读取完毕后，数据将被转换为所需的格式，即一个 char 数组用于存储所有字符串，另一个数组包含每个字符串的起始位置和大小信息。

算法描述

要在 O(n) 时间内对字符串进行排序，需要先仔细考虑才能成功完成。首先，我们注意到对整数键进行排序的一种流行且有效的方法是 基数排序 [1]。我们还注意到 基数 排序可以通过多种方式进行定制。在这种情况下，我们需要对可变长度字符串进行排序，其中可能的值为 A-Z。也就是说，可变长度键，基数为 26。字符 '.' 不被视为可能的值，仅用于辅助处理输入文件中的字符串。

为了完成这个特定的排序问题，我们需要首先根据字符串的长度对字符串进行排序，然后构建一个索引数组，该数组对应于具有给定长度的字符串的子列表。这使我们能够按字母顺序排序，考虑长度大于 w 的字符串，其中 w 将从 k-1 递减到 0。通过这种方式，我们在每次传递时显式地只考虑那些大小足够大的字符串。这直接意味着我们将为当前任务保留 基数 排序的 O(N) 属性。

从代码中可以看到，我们对根据字符串长度排序的字符串进行了正确的基数排序。该例程不使用链表作为存储桶，因为这可能会产生每个存储桶的运行时内存分配开销。我们选择动态分配一个数组，然后从中进行操作。我们首先将一个名为 counts 的数组初始化为零，然后将十六进制数字 i=k-1 到 0 的出现映射到其适当的存储桶，并增加特定数字的出现次数。然后我们遍历并累积相应的索引，这些索引对应于数组 tmp[] 中的正确位置，基于 w'th 位。然后，我们使用创建的索引将元素映射到它们各自的存储桶。完成后，我们将字符串连接起来，将它们从 tmp[] 放入 A[]。当 w == 0 时，我们将根据大小执行基数排序。

一旦列表按大小排序，我们就需要获得长度大于 k-1 到 0 的每个字符串的起始索引。这很简单，因为我们有一个已排序的列表，我们只需应用在 基数 排序的存储桶排序阶段使用的计数机制，然后计算索引。这些索引存储在 sizes[] 中，对应于子列表，这些子列表是任何给定 w 值（在 k-1 到 0 的范围内）的字母 基数 排序每次传递时可以排序的字符串。

然后，我们调用一个专门的 基数 排序来按字母顺序排序，这是通过在任何给定时间仅考虑大小大于 w 的元素来完成的，语句

lower = sizes[w];

允许我们仅考虑子列表中 w'th 个字符，对于足够大的字符串，即实际具有 w'th 个字符的字符串。完成后，在每次传递时，我们将所有内容连接回 A[]，仅考虑从 lower 到 n-1 的那些槽，因为那些是我们已排序的。当 w == 0 时，字符串现在按字母顺序排序。我们还注意到，我们没有改变大小的顺序，因此，字符串 ABS 始终会排在 ABSOLUTE 之前，这是期望的。

注意：此问题的明显错误答案如下：

1. 将字符串显式填充到最大长度字符串的大小会导致 O(n^2) 的运行时。
2. 在某些字符串不够长时，为 w'th 个字符考虑所有字符串。我们可以尝试基于此进行排序，例如，当字符串太短时，考虑一个零字符；然而，这是不正确的，因为当 w 很大时，我们可能会无意中对不需要排序的字符串进行排序。考虑当 n-1 个字符串的大小为 1，而第 n 个字符串的大小为 n 时。这种方法将使算法的复杂度达到 O(n^2)，因为它有效地与填充相同，但没有显式地用零字符增加每个字符串大小的开销。

算法分析

时间复杂度

首先，基于字符串大小的基数排序需要 O(n + k) 的时间。在此特定实现中，k 为 8（当基数为 16 时，8 * 4 => 32 位整数）。这只是一个与 n 无关的常数，因此通过 基数 排序按大小对字符串进行排序是 O(n)。

其次，我们使用一种桶排序的变体，来获得长度为 1, 2, 3, ... k 的元素的起始地址数组。这需要 O(n)。

第三，当我们对字符串进行按字母顺序排序的基数排序时，我们有一个按大小排序的列表，以及一组长度大于 w 的元素的起始地址数组，因此，我们从 w = k - 1（k - 1 是最大长度字符串，LSD 优先）开始，仅考虑长度大于 w 的字符串集，即 lower = sizes[w];。完成后，我们就完成了列表的排序。此例程需要 O(n + k)。尽管 k 的长度会因字符串长度可变而变化，但在每次传递时对 k'th 个字符进行排序时，k 被视为常数，因为只对足够大的子列表进行排序。我们不考虑太小的元素，即当 A[i].T < w 时，我们也不显式地将字符串填充到固定大小。完成后，在每次传递时，我们将结果连接到 A[] 中，仅针对我们已排序的字符串。结合这一点以及 k 与 n 无关的事实，此例程的总时间复杂度将是 O(n)。

因此，我们有 O(n) + O(n) + O(n) 分别用于大小基数排序、索引计数和字母基数排序。该算法的复杂度为 O(n)。

注意：除了考虑 w'th 个字符外，字符串本身不会被触及，w'th 个字符的考虑需要 O(1) 时间，因此它不影响排序。更具体地说，在排序过程中，我们只通过执行 CH(i,w) == C[A[i].S + w] 操作来访问字符串，这需要 O(1) 时间。我们不会移动字符串在 C[] 中的位置，只移动它们的属性 A[]，如讲义所述。

空间复杂度

该算法使用 O(n) 的空间在 C[] 中存储字符串。O(n) 的空间用于在 A[] 中存储字符串的属性（起始索引和大小），并且在算法执行的每个步骤中，即对于上述步骤，我们使用 sizes[]、tmp[] 和 count[] 的数组，其空间分别为 O(k)、O(n)、O(RADIX +1)。总空间复杂度为 O(n)。

Using the Code

该算法使用 Radix-Sort[1] 按大小对字符串进行排序，基数为 16，即十六进制。原因是，我们可以通过 4 的因子进行二进制移位，并与数字 15（在 3,2,1,0 位置上全是二进制一）进行按位掩码运算，以获得下一个十六进制数字（参见 ./include/sort.h）。这比使用 10 作为基数要快得多。但这取决于机器，如果您使用的是大端或小端机器，请定义合适的包含宏。否则，您将无法编译。

文件

            Makefile         -- Makefile to build on Linux/Unix
            f                     -- Sample input file
            include            -- Include directory containing headers
            include/sort.h  -- Header for sorting routines
            include/list.h   -- Header for linked list code
            include/defs.h -- Defines  used by this program
            include/types.h-- Typedefs used by this program
            list.c                -- Linked list code for processing input file f
            main.c             -- function main
            sort.c               -- The Algorithm, and supporting code

参考文献

[1] Sedgewick, R. 1997. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching. 3^rd Edition. Addison-Wesley