在介绍低位优先的字符排序之前先介绍一下“键索引计数法”,有下面一组数据:
姓名 组号
"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
现在需要根据组号对他们进行排序:
分为如下几步:
1:统计组号出现的频率。
2:将频率转换成索引。
3:将数据分类。
4:写回。
例子:
#include <iostream>
using namespace std;
const int Num=20;
struct Student{
string Name;
int GroupNum;
};
int main()
{
string names[Num]={"Anderson","Brown","Davis","Garcia","Harris","Jackson","Johnson","Jones","Martin","Martinez","Miller","Moore","Robinson","Smith","Taylor","Thomas","Thompson","White","Williams","Wilson"};
int groupNum[Num]={2,3,3,4,1,3,4,3,1,2,2,1,2,4,3,4,4,2,3,4};
Student array[Num];
int mid[6]={0};
Student ss[Num];
for(int i=0;i<Num;i++)//初始化
{
array[i].Name=names[i];
array[i].GroupNum=groupNum[i];
}
for(int i=0;i<20;i++)//统计出现的频率
{
mid[array[i].GroupNum+1]++;
}
for(int i=1;i<6;i++)//将频率转换成索引
{
mid[i]+=mid[i-1];
}
for(int i=0;i<Num;i++)//将元素分类
{
ss[mid[array[i].GroupNum]]=array[i];
mid[array[i].GroupNum]++;
}
for(int i=0;i<Num;i++)//输出显示
{
cout<<array[i].Name<<" "<<array[i].GroupNum<<" "<<ss[i].Name<<" "<<ss[i].GroupNum<<endl;
}
}
下面给出低位优先的字符串排序算法(适用于字符串长度一致的情况):
#include <iostream>
using namespace std;
const int Num=20;
class LSD//低位优先
{
public:
void sort(string a[],int w)
{
const int length=Num;
const int R=256;
string mid[length];
for(int i=w-1;i>=0;i--)
{
int count[R+1]={0};
for(int j=0;j<length;j++)//统计出现频率
{
count[a[j].at(i)+1]++;
}
for(int j=0;j<R;j++)//将频率转换成索引
{
count[j+1]+=count[j];
}
for(int j=0;j<length;j++)//将元素分类
{
mid[count[a[j].at(i)]++]=a[j];
}
for(int j=0;j<length;j++)//写回
{
a[j]=mid[j];
}
}
for(int i=0;i<length;i++)
{
cout<<a[i]<<endl;
}
}
};
int main()
{
string Names[Num]={"Robinson","Anderson","Johnson","Brown","Davis","Garcia","Harris","Jackson","Jones","Martin","Martinez","Miller","Moore","Taylor","Thomas","Thompson","White","Williams","Smith","Wilson"};
LSD demo;
demo.sort(Names,5);//5代表使用前5个字符来排序
return 0;
}