-3

我只需要适用于字符串的 c++ 语言中的基数排序实现

我已经有一个适用于普通整数的

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();
    }
}
4

3 回答 3

1

基数排序的函数。 

// 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]);
      }
  }

看看我写的这个博客。那里提供了完整源代码和测试输入文件的下载链接。它非常适合对任意长度的字符串进行排序。解决这个问题时我很痛苦。所以想分享如果它帮助别人。快乐分享。:)

于 2012-10-04T15:50:47.587 回答
0

这是一个可怕的、未经测试的 c 和 c++ 组合，它显示了一种处理字符串的方法。有很多方法可以提高它的清晰度和性能……
首先要解决的是避免在堆栈上创建大量向量的方法。@comingstorm 关于使用两个数组的想法是一个很好的起点。

const int numblocks = 256;
void radixSort(String rsarr[],int length, int offset = 0)
{
  int inplace = 0;
  vector<String> blocks[numblocks];
  //split the strings into bins
  for (int i=0;i<length;i++)
  {
     char c = rsarr[i][offset];
     if (c!='\0')
        blocks[(int)c].push_back(rsarr[i]);
     else //put the null strings up front
        rsarr[inplace++]=rsarr[i];
  }
  //for blocks all except the null terminated one,
  // copy back into original array in order, 
  // then radix sort that portion of the array
  for (int b=1;b<256;b++)  
  {
     for (int j=0;j<blocks[b].length();j++)
       rsarr[inplace++]=blocks[b][j];
     if (j>1)
      radixSort(rsarr[inplace-j],j,offset+1);
  }
}
于 2011-11-22T22:46:01.347 回答
0

尝试对字符串使用基数排序的问题是字符串可以任意长。基数排序实际上只对固定大小的键有意义。

如果作为初始通道，您仍然可以这样做，如果您找到最长字符串的长度（或者，作为细化，第二长字符串），然后从该位置开始进行基数迭代。

请注意，您可以仅使用源数组和目标数组——在迭代之间交换它们，而不是每次基数迭代保存一个数组。

于 2011-11-22T21:49:52.413 回答