在 Programming Pearls 中有一种算法可以对不同长度的数组进行排序,但排序的时间与它们的长度之和成正比。例如,如果我们有一个记录数组x[0...n-1]
,并且每条记录都有一个整数长度和一个指向数组的指针bit[0...length-1]
。
代码是这样实现的:
void bsort(l, u, depth){
if (l >= u)
return ;
for (i = l; i <= u; i++){
if (x[i].length < depth)
swap(i, l++);
}
m = l;
for (int i = l; i < u; i++){
if (x[i].bit[depth] == 0)
swap(i, m++);
}
bsort(l, m - 1, depth + 1);
bsort(m, u, depth + 1);
}
我的问题是,鉴于记录:
x[6] = {"car", "bus", "snow", "earth", "dog", "mouse"}
我知道如何获取字符串长度,但是使用位数组呢?我怎样才能制作一个适合这个字符串数组的位数组?甚至x[i].bit[depth]
我该如何实现呢?