0

我非常接近让这个程序工作，但我试图让这个程序使用基数排序按字母顺序排列一组字符串，并且在弄清楚如何

void msd(string* sortMe)
{
    aux = new string[numElements];  //Set size of the array used to sort each character.
    msd(sortMe, 0, numElements, 0);
}

void msd(string* sortMe, int l, int r, int d) //Here I use key-indexed     counting :http://algs4.cs.princeton.edu/lectures/51DemoKeyIndexedCounting.pdf
{
    if(r < l || r == l) return; //if we get to 1 left, it is sorted
    int count[256+1]= {0};  //256 because we are using ASCII. + 1 for key-indexed counting
    for(int i =0; i < numElements; i++)
    {
         count[sortMe[i][d] + 1]++;   //For each letter found, you must put it in the ascii code + 1
    }
    for(int k = 1; k < 256; k++)    //Everything but null
    {
         count[k] += count[k-1];     //Get cumulates(everything before added together + what it is)
    }
    for(int i =0; i < numElements; i++)
    {
         aux[count[sortMe[i][d]]++] = sortMe[i]; //using your count array, you must move over elements from sortMe, to the aux array
    }
    for(int i = 0; i < numElements; i++)
    {
         sortMe[i] = aux[i];      //Then you must copy the elements from the aux array back to the main array.
    }
    for(int i = 0; i< numElements; i++)
    {
         cout<< aux[i]<< endl;
    }
    for(int i = 0; i < 255; i++)
    {
         msd(sortMe, l + count[i], l+ count[i+1], d+1); //You must then call recursively. The count array when finished, will give you what indexes(sub arrays to sort) you must sort between. Also, you are moving to the next character in the string(d)
    }
}

第一次迭代效果很好，并按第一个字符对所有字符串进行排序。但是，第二次迭代将所有这些都抛到了窗外，并按第二个字符对它们进行排序。如何解决此问题以使其正常工作？

4

0 回答 0