QuickSort扮演好笑

Question

我有一个类WordList包含一个字符串（单词）的向量。矢量长度为88994，我试图用快速排序对它进行排序。当我运行我的代码时，它将它分类得很好，但是一些元素看起来不合适。例如，一切都按照字母顺序排列，但一个词将不合适......这会发生几次。有什么我没有执行的权利？

void WordList::quickSort(int start, int end){ 
    if(start < end){ 
     int pivot = partition(start, end); 
     quickSort(start, pivot-1); 
     quickSort(pivot+1, end); 
    } 

} 

int WordList::partition(int start, int end){ 
    int pivot = end; 
    int leftList = start-1; 
    for(int j = start; j < (end - 1); j++){ 
     if(LoWords[j].compare(LoWords[pivot]) <= -1){ 
      leftList++; 
      string temp = LoWords[leftList]; 
      LoWords[leftList] = LoWords[j]; 
      LoWords[j] = temp; 

     } 
    } 
    string anotherTemp = LoWords[leftList+1]; 
    LoWords[leftList+1] = LoWords[end]; 
    LoWords[end] = anotherTemp; 

    return leftList+1; 

} 

Answer 1

我认为你必须改变你的分区算法弄成这个样子：

#include <iostream> 
#include <vector> 
#include <string> 

using std::vector; 
using std::string; 

// I don't have your class, so I'll use a global variable to keep your signature 
vector<string> words{ 
    "mouse", "APU", "CPU","mainboard", "SATA", "hard drive", "GPU", "fan", "case" 
}; 

int partition(int start, int pivot) { 
    int i = start; 
    int j = pivot - 1; 
    while (i <= j) { 
     if (words[j] > words[pivot]) { 
      --j; 
      continue; 
     } 
     if (words[i] <= words[pivot]) { 
      ++i; 
      continue; 
     } 
     if (i < j) { 
      // You can use std::swap(words[i],words[j]); from <algorithm> instead 
      auto temp = words[i]; 
      words[i] = words[j]; 
      words[j] = temp; 
      ++i; 
      --j; 
     } 
    } 
    // or std::swap(words[pivot],words[j+1]); 
    auto temp = words[pivot]; 
    words[pivot] = words[j + 1]; 
    words[j + 1] = temp; 
    return j + 1; 
} 

void quickSort(int start, int end) { 
    if(start < end) { 
     int pivot = partition(start, end); 
     quickSort(start, pivot - 1); 
     quickSort(pivot + 1, end); 
    } 
} 

int main() { 

    quickSort(0, words.size() - 1); 

    for (auto & i : words) 
     std::cout << i << '\n'; 

    return 0; 
} 

编辑

为了让你的函数的工作，我认为你必须改变路线

for(int j = start; j < (end - 1); j++) { ... 

into

for(int j = start; j < end; j++) {...