字符串排序-低位优先(LSD)

时间:2022-02-03 09:05:26

在介绍低位优先的字符排序之前先介绍一下“键索引计数法”,有下面一组数据:

    姓名                  组号

"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;
}
}
字符串排序-低位优先(LSD)
下面给出低位优先的字符串排序算法(适用于字符串长度一致的情况):

#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;
}
字符串排序-低位优先(LSD)