如何用基数排序可变长度字符串数组？
我知道基排序可以对相同长度的字符串数组进行排序，但是否可以使用可变长度的字符串进行排序。如果是的话，C族代码或伪代码是什么来实现这一点呢？
对于可变长度的字符串，它可能不是一个快速算法，但是实现基排序很容易，所以如果需要快速编码排序，它是有用的。
回答 2
Stack Overflow用户
发布于 2015-06-13 04:01:03
我不太清楚您所说的“可变长度字符串”是什么意思，但是您可以就地执行二进制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);
}
Stack Overflow用户
发布于 2018-01-06 20:33:01
您可以对可变长度的字符串进行MSB第一次基排序.有几个不明显的细节：
根据strveci，Pass #N将把(分散)字符串从输入向量分割到256个分区。然后，它将扫描分区的顺序，并将(重新插入)字符串返回到输入向量。
现在稍微复杂的一点..。
当你到达字符串的末尾时，它处于最后的位置，不应该再被碰触。它将前后的字符串分割成不同的范围。每次传递的结果是一组尚未排序的行的范围。
这意味着在第一个区域之后传递#N，扫描每个范围中的字符串，并将源范围id (index)和字符串一起存储在分区中。在“重新插入”步骤中，它将字符串放回其源范围；并且再次生成一组新的未排序行范围。
如果向前扫描输入范围，然后向后扫描分区，然后从每个源范围的后面重新插入，则保持基排序的稳定排序加值。
您也可以使用递归(从零开始对任何子范围进行完整排序)，但是上面的设置节省了设置，而且速度更快。
还有更多细节..。快速排序通过对微小范围进行插入排序(例如，最多16次)；基数排序从同样的范围中受益。可以使用多个字节作为分区索引。其中一种方法是：基类-米沙桑德堡-2010还有其他方法。对不起，我不能贴代码；它现在是专有的。
https://stackoverflow.com/questions/30794728
复制相似问题
腾讯云开发者
