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++) {...