板藍根在C++中的排序實現字符串

Question

我只需要在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(); 
    } 
} 

Answer 1

與試圖使用的問題之一字符串的基數排序是字符串可以任意長。基數排序對於固定大小的鍵實際上只有意義。

如果作爲初始傳遞找到最長字符串的長度（或作爲細化，第二長的字符串），則仍然可以這樣做，然後從該位置開始進行基數迭代。

請注意，不是每個基數迭代都保存一個數組，只能使用源和目標數組 - 在迭代之間交換它們。

Answer 2

這是一個可怕的未經測試的c和C++混合，它展示了一種處理字符串的方法。 有很多方法可以改善它的清晰度和性能......
首先要解決的問題是避免在堆棧上創建大量向量的方法。 @即興風格的關於使用兩個數組的想法是一個很好的開始。

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

Answer 3

基數排序的函數。

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

看一看here in this blog that I have written。下載鏈接的完整源代碼和測試輸入文件在那裏可用。它對於排序任意長度的字符串非常有效。解決這個問題時我有很多痛苦。所以如果能幫助別人的話，那麼就分享吧。快樂分享。 :)