Radix排序在c ++中实现为字符串 [英] Radix sort implemented in c++ for string
本文介绍了Radix排序在c ++中实现为字符串的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我只需要用于字符串的c ++语言中的radix排序实现
i just need radix sort implementation in c++ language which works for strings
我已经有一个适用于正常整数的
i already have the one which works for normal integers
vector < vector < int> > blocks[7];
void radixSort(int rsarr[],int length){
int index;
vector<int> helper;
vector< vector<int> > helper2;
for(int e=0;e<10;e++){
helper2.push_back(helper);
}
for(int r=0;r<7;r++){
blocks[r]=helper2;
}
for(int y=0;y<length;y++){
index=(int)(rsarr[y])%10;
blocks[0][index].push_back((rsarr[y]));
}
for(int j=1;j<7;j++)
{
for(int k=0;k<10;k++)
{
for(int i=0;i<blocks[j-1][k].size();i++)
{
index=(int)(blocks[j-1][k][i]/pow(10,j))%10;
blocks[j][index].push_back(blocks[j-1][k][i]);
}
}
}
int q=0;
for(int f=0;f<blocks[6][0].size();f++){
rsarr[q]= blocks[6][0][f];
q++;
}
if(blocks[6][1].size()==1)
{
rsarr[q]=blocks[6][1][0];
}
for(int z=0;z<7;z++)
{
blocks[0].clear();
}
}
推荐答案
用于基数排序。
// this is the sort function which call the radixSort Function.
void Datastructure::sort()
{
vector<string> tempOneDimWordList;
tempOneDimWordList = WordList;
WordList.clear();
radixSort(tempOneDimWordList, (unsigned int)tempOneDimWordList.size(), 0);
}
// MSD radix function definition to sort words
//lexicgraphically using most significat bits.
void Datastructure::radixSort(vector<string> tempOneDimWordList,
unsigned int oneDimVecSize, unsigned int offset)
{
if(offset == lengthOfMaxWord.length ){
return;
}
vector<string> towDimWordlist [MAX_LENGTH];
for (unsigned int i = 0; i < oneDimVecSize; i++){
if(offset < tempOneDimWordList[i].size()){
char c = tempOneDimWordList[i][offset];
if (c != '\0'){
towDimWordlist[(((unsigned int)c) )].
push_back(tempOneDimWordList[i]);
}
}
else{
WordList.push_back(tempOneDimWordList[i]);
}
}
// this loop is used to call the function recursively
// to sort the words according to offset.
for (unsigned int i = 0; i < (unsigned int)MAX_LENGTH; i++) {
unsigned int sizeCheck = (unsigned int)towDimWordlist[i].size();
if (sizeCheck > 1){
radixSort(towDimWordlist[i], sizeCheck, offset+1);
}
else if(sizeCheck == 1)
{
WordList.push_back(towDimWordlist[i][0]);
}
}
查看这里在我写的这个博客。下载链接的完整源代码和测试输入文件可用。它工作真的很好排序任意长度的字符串。我在解决这个问题时有很多痛苦。所以想想分享如果它帮助别人。快乐分享。 :)
Have a look here in this blog that I have written. Download link of the full source code and test input files are available there. It works really fine for sorting strings of arbitrary length. I had lots of pain while solving this problem. So thought to share if it helps someone else. Happy sharing. :)
这篇关于Radix排序在c ++中实现为字符串的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文