Radix按字符串数组排序？

Question

我一直在研究,虽然我已经想出了使用Radix Sort来按字母顺序排列字符串数组的一般想法,但我知道我的方向是错误的.

这是我到目前为止:

void radixSort(string* sortMe, int l)
{
    queue<string>* sections = new queue<string>[27];    //Have a-z, and also one for strings that are null terminated.
    for(int i = 0; i < numElements; i++)
    {
        if(!(sortMe[i][l] == 32))
            sections[sortMe[i][l]-96].push(sortMe[i]);      //-96 because the ascii code for a is 97. If, for example a is the character, it will be placed at 1. 0 is left for null characters
    }

    for(int i =0; i < 26; i++)
    {
        while(!sections[i].empty())
        {
            temp.push_back(sections[i].front());
            sections[i].pop();
        }
    }
}

到目前为止我用第一个字符对所有字符串进行排序,我知道然后我必须完成剩余字符的子数组并对它们进行排序,但是如何有效地实现呢？字符串大小可变,可以包含空格,例如:

• 细分
• 主要街道
• 裤子
• 刺穿了非殖民化
• 泥质
• 轴向令人满意
• 个性倔强的
• 过敏症
• 熊
• hairbreadths
• 面霜激增
• unlaboured
• 印第安纳州
• buggiest
• 毛里塔尼亚
• 射气
• 赞歌
• zouaves洗碗盘
• 拖曳
• solarisms
• remunerativeness
• 溶
• 轮廓分明
• 颈静脉
• ooziness
• toastier
• 波特
• 后缀
• 无能为力的潮汐
• disassimilated
• 喘气
• flirtier
• 呃

这是我发现它似乎有用的东西:http: //algs4.cs.princeton.edu/lectures/51DemoKeyIndexedCounting.pdf

Answer 1

你发现的幻灯片很棒!但是这些队列在哪里来自你的代码？

无论如何,你在这里(实例):

template <typename E>
size_t bin(const E& elem, size_t digit)
{
    return elem.size() > digit ? size_t(elem[digit]) + 1 : 0;
}

template <size_t R, typename C, typename P>
void radix_sort(P& pos, const C& data, size_t digit)
{
    using A = std::array<size_t, R + 1>;
    A count = {};
    P prev(pos);

    for (auto i : prev)
        ++count[bin(data[i], digit)];

    A done = {}, offset = {{0}};
    std::partial_sum(count.begin(), count.end() - 1, offset.begin() + 1);

    for (auto i : prev)
    {
        size_t b = bin(data[i], digit);
        pos[offset[b] + done[b]++] = i;
    }
}

struct shorter
{
    template <typename A>
    bool operator()(const A& a, const A& b) { return a.size() < b.size(); }
};

template <size_t R, typename C>
std::vector<size_t> radix_sort(const C& data)
{
    std::vector<size_t> pos(data.size());
    std::iota(pos.begin(), pos.end(), 0);

    size_t width = std::max_element(data.begin(), data.end(), shorter())->size();

    for (long digit = long(width) - 1; digit >= 0; --digit)
        radix_sort<R>(pos, data, size_t(digit));

    return pos;
}

你可以这样使用

int main()
{
    std::vector<std::string> data = generate();
    std::vector<size_t> pos = radix_sort<128>(data);
    for (auto i : pos)
        std::cout << data[i] << std::endl;
}

其中generate()包含在实例中并生成问题中给出的字符串.

我不是要解释这是如何工作的,我假设你可以弄清楚,因为你正在研究这个问题.但是有一些评论是有条不紊的.

• 我们既没有就地输入序列,也没有返回已排序的副本; 我们只是返回排序序列中输入元素的一系列位置.

• 我们正在从右到左处理字符串.

• 复杂度O(lw),其中l是输入长度(输入字符串的数目),并w为最大输入宽度(最大长度的所有输入的字符串).因此,如果字符串宽度变化不大,则此算法有意义.

• 第一模板参数R的radix_sort()是用于在输入每个数字(字母)的可能值的数目.例如,R = 128意味着可能的值0..127.这应该适合您的输入.我没有尝试过对ASCII代码做任何聪明的事情,但你可以自定义功能bin().

• 在输出中bin(),value 0保留为表示"我们已超过此字符串的结尾".这些字符串放在仍在继续的其他字符串之前.

• 我试图给变量和函数提供不言自明的名称,并尽可能使用标准库调用来执行常见任务.

• 代码是通用的,例如,它可以对包含随机访问容器的任何随机访问容器进行排序,而不仅仅是字符串向量.

• 我在这里和那里使用C++ 11的功能是为了方便,但没有什么是真正必要的:一个人可以很容易地用C++ 03做同样的事情.