使用C ++实现QuickSort的问题

Question

因此，对于这个简单的代码，答案结果是部分正确的。结果是“1 1 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循环。在for循环完成后应更新i值，然后使用i值进行交换和其他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;

}

Answer 2

就像@Loc Tran指出的那样，你的枢轴交换以及随后的左右快速排序必须在for循环之外。不需要else continue;。 for循环的目的是找到我们的i元素的位置（pivot），使得左边的所有元素都小于pivot，而右边的元素大于pivot。

一旦确定了位置（i+1），就可以通过交换将枢轴放在那里，然后在pivot的左右两侧快速排序。

此外，你应该只在low < high时快速排序。

#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]);
        }
    }
    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;

}