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

Question

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

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

Answer 1

我不太确定“可变长度字符串”是什么意思，但您可以就地执行二进制 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);
}