快速排序不对字符串列表中的一个元素进行排序

Question

谁能告诉我我的代码有什么问题：

int Partition(vector<string>& userIDs, int i, int k) {
    int pivot = (i + (k - i) / 2);
    string temp;
    
    while(i<k) {
        cout << "pivot:" << pivot << endl;
        while (userIDs.at(i).compare(userIDs.at(pivot))<0) {
            cout << "1. i:"<<i<<" UserIDs.at(i):" << userIDs.at(i) << " UserID.at(pivot): " << userIDs.at(pivot) << endl;
            i += 1;
        }
        while (userIDs.at(pivot).compare(userIDs.at(k))<0) {
            cout << "2. k:" << k << " UserIDs.at(k):" << userIDs.at(k) << " UserID.at(pivot): " << userIDs.at(pivot) << endl;
            k -= 1;
        }

        if(i<k){
            cout << "3. i:" << i << " k:"<<k<<" UserIDs.at(i):" << userIDs.at(i) << " UserID.at(k) : " << userIDs.at(k) << endl;
            temp = userIDs.at(i);
            userIDs.at(i) = userIDs.at(k);
            userIDs.at(k) = temp;
            i++;
            k--;
        }
        cout << "4. i:" << i << " k:" << k << endl;
    }
    cout << " 5. k:" << k << endl;
    return k;
}

void Quicksort(vector<string>& userIDs, int i, int k) {
    cout << "Quicksort i:" << i << " k:" << k << endl;
    if (i >= k) {
        return;
    }
    int lowEndIndex = Partition(userIDs, i, k);
    cout << "Quicksort lowEndIndex:" << lowEndIndex << endl;
    Quicksort(userIDs, i, lowEndIndex);
    Quicksort(userIDs, lowEndIndex+1, k);
}

当我输入这个列表时：

BigBen
GardenHeart
GreyMare
TeenPunch
WhiteSand
LifeRacer
Doom
AlienBrain

我得到：

AlienBrain
BigBen
GreyMare
GardenHeart
Doom
LifeRacer
TeenPunch
WhiteSand

为什么 Doom 不在正确的位置？

Answer 1

#include <bits/stdc++.h>
using namespace std;

int Partition(vector<string>& userIDs, int i, int k) {
    int pivot = i;
    string pivotValue = userIDs[pivot];
    string temp;

    int leftIndex = i;
    int rightIndex = k;
    

    while(i<k) {
        while (userIDs[i].compare(pivotValue)<=0) {
            i++;
            if(i >= rightIndex) break;
        }
        while (pivotValue.compare(userIDs[k])<=0) {;
            k--;
            if(k <= leftIndex) break;
        }

        if(i<k){
            temp = userIDs[i];
            userIDs[i] = userIDs[k];
            userIDs[k] = temp;
        }

        
    }
            // swap
    userIDs[pivot] = userIDs[k];
    userIDs[k] = pivotValue;
    
    return k;
}

void Quicksort(vector<string>& userIDs, int i, int k) {
    if (i >= k) {
        return;
    }

    int lowEndIndex = Partition(userIDs, i, k);
    Quicksort(userIDs, i, lowEndIndex - 1);
    Quicksort(userIDs, lowEndIndex + 1, k);
}

int main() {
    
    vector<string> userIDs = {"BigBen", "GardenHeart", "GreyMare", "TeenPunch",
    "WhiteSand", "LifeRacer", "Doom", "AlienBrain" };

    Quicksort(userIDs, 0, userIDs.size() - 1);
    

    for(auto& c: userIDs) cout << c << " ";
    cout << endl;
    return 0;
}

修复了代码并进行了测试。现在可以了。有什么问题？
据我所知，首先你没有在 while 循环中放置 break() 语句，以防 i 或 k 超出向量的边界。我已经将枢轴从中间元素更改为第一个元素，但这只是我的偏好，您可以在中间使用枢轴来实现快速排序算法，这没什么大不了的。我先用 lowEndIndex - 1 调用了 Quicksort() 而不是 lowEndIndex。我使用了 [] 运算符而不是 at()，但这也是我的偏好。我想主要问题是 break 东西和用 lowEndIndex 而不是 lowEndIndex - 1.

调用快速排序方法

输出：

AlienBrain BigBen Doom GardenHeart GreyMare LifeRacer TeenPunch WhiteSand

快速排序不对字符串列表中的一个元素进行排序

Quicksort not sorting one element in the list of strings

c++

sorting

algorithm

quicksort