算法C++ 字符串排序键索引计数法排序示例代码实现+算法理解（第五章）

63 阅读 0 评论 42 点赞

我是靠谱客的博主无情宝马，最近开发中收集的这篇文章主要介绍算法C++ 字符串排序键索引计数法排序示例代码实现+算法理解（第五章），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 造轮子博客链接
- 前引
- 我的理解
- 字符串排序键索引示例
- 代码实现
- 实现效果

造轮子博客链接

算法第四版C++算法实现全集

前引

这一章也是算法第四版的最后一章了
在我打算把这本书看完后也要进入学习计算机庞大知识体系的书籍中了
而且在写下这些代码中我并不认为这些代码在半年一年后
我是记得的但我依然还是打算花时间写
毕竟也不是很困难而且代码这个东西
写了就是写了没写就是没写

写了那些东西就是属于你自己的
哪怕忘了也是无所谓的这些代码还是属于自己的而且总归是有点印象的
但是只是看书不敲代码那百分之百是看了就忘且学且记

我的理解

这个算法我觉得是这个样子的
灵魂之处就在于
我们是怎么把一个一个位置放上去的呢

我们通过一次遍历把每个数字的频率记录了下来
然后我们通过累加操作把每个数中这些小于这个数的个数求出来了
举个例子
比如我们求出来
1的频率数为2
2的频率数为5
3的频率数为10

那么我们求出来比如比2的小的数频率共有2个
比3小的数频率共有2+5 = 7个
那么ok
我们放入序号为2的时候我们是不是从数组的2号位置开始放呢
我们放入序号为3的时候我们是不是从数组的7号位置开始放呢
因为2号数字前面就一共2个比他小的
3号数字前面就7个比他小的而且这样放了之后把序号+1
后面的2号数字和3号数字依次放就好了
并且还是有序的

字符串排序键索引示例

这些示例全部来自于书上《算法第四版 5.1字符串排序》
我只是一个一个敲上去了方便读者自己调试：）

pair<string,int> temp[] = {{"Anderson",2},{"Brown",3},
{"Davis",3},{"Garcia",4},{"Harris",1},
{"Jackson",3},{"Johnson",4},{"Jones",3},
{"Martin",1},{"Martinez",2},{"Miller",2},{"Moore",1},
{"Robinson",2},{"Smith",4},{"Taylor",3},{"Thomas",4},
{"Thompson",4},{"White",2},{"Williams",3},{"Wilson",4}};

代码实现

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;

int main()
{
    pair<string,int> temp[] = {{"Anderson",2},{"Brown",3},{"Davis",3},{"Garcia",4},{"Harris",1},{"Jackson",3},{"Johnson",4},{"Jones",3},{"Martin",1},
                    {"Martinez",2},{"Miller",2},{"Moore",1},{"Robinson",2},{"Smith",4},{"Taylor",3},
                    {"Thomas",4},{"Thompson",4},{"White",2},{"Williams",3},{"Wilson",4}};
    vector<pair<string,int>> names;
    for(const auto& pair:temp)  names.emplace_back(pair);

    int size = names.size();
    vector<int> count(6,0);
    vector<int> sorted_nums(size);

    for(const auto& name:names)  ++count[name.second+1];
    for(int i=1;i<=4;++i)   count[i] += count[i-1];

    for(int i=0;i<size;++i)   sorted_nums[count[names[i].second]++] = i;
    for(const auto& num:sorted_nums)
        cout<<names[num].first<<' '<<names[num].second<<endl;

    return 0;
}