使用快速排序来排序字符串

Question

我遇到问题实施排序字符串数组的快速排序。我对C++也比较陌生，所以仍然在努力解决一些问题。现在我的代码正确地读入并创建了一个字符串数组，但是当我尝试使用我的快速排序算法时遇到问题。我遇到的第一个问题是，我相信递归并不会停止。快速排序运行一小段后，我得到一个分段错误。

代码（修改）：

#include "MyParser.h" 
    #include <iostream> 
    #include <fstream> 
    #include <string> 

    void resize(string*& words, int size) 
    { 
    string* newArray = new string[size*2]; 

    for (int i = 0; (i < size)&&(i<size*2); i++) 
     newArray[i] = words[i]; 

    for (int i = size; i < size*2; i++) 
    newArray[i] = ""; 

    delete[] words; 
    words = newArray; 
    } 

    void partitionArray(string*& words, int& left, int& right, int pi) 
    { 
    int i = left; 
    int j = right; 
    string tmp; 
    string pivot = words[pi]; 
    while (i < j) { 
     string str1 = words[i]; 
     string str2 = words[j]; 
     while ((str1.compare(pivot) < 0) && (i < right)) 
      i++; 
     while ((str2.compare(pivot) >= 0) && (j > left)) 
      j--; 
     if (i <= j) 
     { 
      tmp = words[i]; 
      words[i] = words[j]; 
      words[j] = tmp; 
      i++; 
       j--; 
      } 
     }; 
    } 

    void quickSort(string*& words, int left, int right) 
    { 
     int i = left; 
     int j = right; 
     string tmp; 
     string pivot = words[(left + right)/2]; 
     /* partition */ 
     int pivotIndex = (left + right)/2; 
     pivotIndex = partitionArray(words, 0, right, pivotIndex); 
     cout << "start recursion" << endl; 
     /* recursion */ 
     if (left < j) 
      quickSort(words, left, j); 
     if (i < right) 
      quickSort(words, i, right); 
    } 

    int main() 
    { 
     // define file reader 
     ofstream outData; 
     outData.open("logData.txt"); 

     Parser* myParser = new Parser("testData.txt"); 
     int sizeOfArray = 500; 
     string* words = new string[sizeOfArray]; 
     int index = 0; 
     while(myParser->hasTokens()) 
     { 
      if (index >= sizeOfArray) 
      { 
       resize(words, sizeOfArray); 
       sizeOfArray = sizeOfArray*2; 
      } 
      string currentWord = myParser->nextToken(); 
      if (currentWord != "") 
      { 
       words[index] = currentWord; 
       index++; 
      } 
     } 
     int lastWordInArrayIndex = index; 
     quickSort(words, 0, lastWordInArrayIndex); 
     return 0; 
    } 

任何帮助将不胜感激！

改进

现在它将在以下11个要素正确排序： adfgh btyui dfghj eerty fqwre kyuio verty wwert yrtyu zbsdf zsdfg

但尝试时对以下解析的文本进行排序，从所有分隔符中解脱出来，但更糟的是“像这样”，只用一个连字符或带有apostro的单词PHE像“他们”，它不会终止：吵架后

三天，王子斯捷潘·阿尔卡季奇 奥布隆斯基 - STIVA，因为他在时尚天下 - 叫他平时小时就醒了，也就是在 早上八点，不在他妻子的卧室里，而是在他学习的皮革覆盖的 沙发上。他把他那粗壮，精心照顾的人翻过来，好像他会沉睡在长长的睡梦里;他大力拥抱另一边的枕头 ，并埋在他的脸上;但一下子他就跳起来，坐在沙发上坐起来 ，睁开了眼睛。

“是的，是的，现在怎么样？”他想，想要完成他的梦想。 “现在，它是怎么回事？可以肯定的！阿拉宾在达姆施塔特晚餐;不，不是达姆施塔特，但是美国的东西，是的，但是 然后，达姆施塔特在美国，是的，阿拉宾吃晚餐 玻璃桌子和桌子唱着，Il mio tesoro - 虽然不是Il mio tesoro，但是更好的东西，还有一些 桌上的小滗水器，他们也是女性，“他记得 。

再次对这个问题的任何帮助将不胜感激！

Answer 1

你quickSort功能确实会递归无限期：

void quickSort(string*& words, int left, int right) 
{ 
    int i = left; 
    int j = right; 

    ... 

    if (left < j) 
     quickSort(words, left, j); 
    if (i < right) 
     quickSort(words, i, right); 
} 

i，j，left和right没有在该函数的任何地方修改，所以如果left < right的功能将被递归使用相同的参数一再呼吁。