c++ - 使用 C++ 实现 QuickSort 的问题

Question

因此对于这个简单的代码，答案被证明是部分正确的。结果是“11个2个3个4个4个2个6个8个5个“ 我认为问题应该与递归和分区有关。我哪里做错了？？

#include <iostream>

using namespace std;


void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int num[], int low, int high){
    int i = low - 1;
    int pivot = num[high];
    for(int j = low; j <= high -1; j++){
        if(num[j] <= pivot){
            i++;
            swap(&num[i], &num[j]);
        }
        else{
            continue;
        }
    swap(&num[i+1], &num[high]);
    quick_sort(num, low, i);
    quick_sort(num, i+2, high);
    }
}

int main(){
    int test[] = {3,1,2,6,5,4,8,1,2,4};
    quick_sort(test, 0, sizeof(test)/sizeof(test[0])-1);
    for(int i = 0; i < sizeof(test)/sizeof(test[0]); ++i){
        cout << test[i] << endl;
    }
    return 0;

}

Answer 1

您的问题是 for 循环。 i 值应在 for 循环完成后更新，然后使用 i 值进行 swap 和其他 quick_sort 调用。但是您的源代码，我在 for 循环内部进行了更新，并将其用于交换和其他 quick_sort 调用。这是问题所在。这是我的解决方案:

#include <iostream>

using namespace std;


void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int num[], int low, int high) {
    if (low >= high) return;
    int i = low - 1;
    int pivot = num[high];
    for (int j = low; j <= high - 1; j++) {
        if (num[j] <= pivot) {
            i++;
            swap(&num[i], &num[j]);
        }
        else {
            continue;
        }
    } // move to correct line
    swap(&num[i + 1], &num[high]);
    quick_sort(num, low, i);
    quick_sort(num, i + 2, high);
    // } this line should be moved to another line
}

int main() {
    int test[] = { 3,1,2,6,5,4,8,1,2,4 };
    quick_sort(test, 0, sizeof(test) / sizeof(test[0]) - 1);
    for (int i = 0; i < sizeof(test) / sizeof(test[0]); ++i) {
        cout << test[i] << endl;
    }
    return 0;

}