如何使用基数排序对可变长度字符串数组进行排序？

Question

我知道基数排序可以对相同长度的字符串数组进行排序，但是否可以对可变长度的字符串进行排序。如果是，实现它的 C 系列代码或伪代码是什么？

对于可变长度字符串，它可能不是一个快速算法，但它很容易实现基数排序，因此如果需要快速编码排序，它很有用。

Answer 1

我不太确定你所说的 "variable-length strings" 是什么意思，但你可以就地执行二进制 MSB 基数排序，因此字符串的长度并不重要，因为没有中间桶。

#include <stdio.h>
#include <algorithm>

static void display(char *str, int *data, int size)
{
    printf("%s: ", str);

    for(int v=0;v<size;v++) {
        printf("%d ", data[v]);
    }

    printf("\n");
}

static void sort(int *data, int size, int bit)
{
    if (bit == 0)
        return;

    int b = 0;
    int e = size;

    if (size > 0) {
        while (b != e) {
            if (data[b] & (1 << bit)) {
                std::swap(data[b], data[--e]);
            }
            else {
                b++;
            }
        }

        sort(data, e, bit - 1);
        sort(data + b, size - b, bit - 1);
    }
}

int main()
{
    int data[] = { 13, 12, 22, 20, 3, 4, 14, 92, 11 };
    int size = sizeof(data) / sizeof(data[0]);

    display("Before", data, size);
    sort(data, size, sizeof(int)*8 - 1);
    display("After", data, size);
}

Answer 2

您可以对可变长度字符串进行 MSB 优先基数排序。有几个不明显的细节：

根据 strvec[i][N]，传递 #N 会将输入向量中的字符串划分（分散）为 256 个分区。然后它将按顺序扫描分区，并将字符串放回（重新插入）到输入向量中。

现在有点复杂...

当你到达一个字符串的末尾时，它就在它的最终位置，永远不应该再被触及。这会将其前后的字符串拆分为单独的 RANGES。每次传递的结果是一组范围内的尚未排序的行。

这意味着在第一个之后传递 #N，扫描每个范围中的字符串，并将源范围 ID（索引）与字符串一起存储在分区中。在 "reinsert" 步骤中，它将字符串放回其源范围；再次，它生成一组新的未排序行范围。

如果您向前扫描输入范围然后向后扫描分区并从每个源范围的后面开始重新插入，您将保留基数排序的稳定排序优势。

您也可以使用递归（在任何子范围内从头开始进行完整排序），但上面的方法节省了设置并且速度更快。

还有更多细节……快速排序失败了，对小范围（例如最多 16）进行插入排序；基数排序从做同样的事情中受益。可以使用多个字节作为分区索引。一种方法是：Radix Sort-Mischa Sandberg-2010 还有其他方法。抱歉，我不会 post 代码；它现在是专有的。

如何使用基数排序对可变长度字符串数组进行排序？

How to sort a variable-length string array with radix sort?

sorting

string

algorithm

radix-sort