低位优先排序

struct node{
    string tmp;
    int num;
};
int main(int argc, char *argv[])
{
    node nn[6] = {
        { "A", 2 },
        { "B", 3 },
        { "C", 3 },
        { "D", 1 },
        { "E", 2 },
        { "F", 3 },
    };
    int cnt[4] = { 0 };
    for (int i = 0; i < 6; i++)
    {
        cnt[nn[i].num]++;
    }
    for (int i = 0; i < 4; i++)
    {
        cnt[i + 1] += cnt[i];
    }
    node res[6];
    for (int i = 0; i < 6; i++)
    {
        res[cnt[nn[i].num-1]++] = nn[i];
    }
    for (int i = 0; i < 6; i++)
    {
        cout << res[i].tmp << " " << res[i].num << endl;
    }

    return 0;
}

低位优先排序，根据键的索引来分组排序。

步骤是：

1.频率统计

2.频率转换为索引

3.数据排序

对于上面的例子（我没有完全按照《算法》一书来写，不过思路是一样的）。可以发现：

比如

        { "A", 2 },
        { "B", 3 },
        { "C", 3 },
        { "D", 1 },
        { "E", 2 },
        { "F", 3 },

频率分布为1个1组，2个2组，3个3组。

所以计算后的索引应该是：

0,1,3.

0位置放一组，1位置放置两个二组，3位置放三个三组。

每放一个元素，索引表就加1.这样就可以把数组排序。