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.这样就可以把数组排序。
原文：http://www.cnblogs.com/wyc199288/p/6361385.html