QuickSort 表现得很有趣

Question

我有一个 class 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++) { ...

进入

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

QuickSort 表现得很有趣

QuickSort acting funny

c++

quicksort