C++ QuickSort 实现，可对除单个元素之外的所有元素进行排序

Question

这是我第一次写C++。我正在尝试实现引用 MIT open course ware slides（特别是幻灯片 4 和 17）的 QuickSort。

但是，有一个错误：

input:  6 10 13 5 8 3 2 11 
output: 2 5 3 6 8 11 10 13

我不确定为什么 5 不合适。我的代码似乎完美地反映了幻灯片。

#include <utility>

using namespace std;

template <typename T>
void print_array(T &arr) {
    for (int i : arr) {
        cout << i << " ";
    }
    cout << endl;
}

int partition(int* a, int p, int q) {
    int x = a[p];
    int i = p;
    for (int j = p+1; j < q; j++) {
        if (a[j] <= x) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[p], a[i]);
    return i;
}

void quicksort(int* a, int p, int r) {
    if (p < r) {
        int q = partition(a, p, r);
        quicksort(a, p, q-1);
        quicksort(a, q+1, r);
    }
}

int main() {
    int keys[8] = {6, 10, 13, 5, 8, 3, 2, 11};
    print_array(keys);
    quicksort(keys, 0, 8);
    print_array(keys);
    return 0;
}

Answer 1

幻灯片显示 for j ← p + 1 to q，您转向 for (int j = p+1; j < q; j++)。这是一个 off-by-one 错误。

C++ QuickSort 实现，可对除单个元素之外的所有元素进行排序

C++ QuickSort implementation that sorts everything but a single element

c++

sorting

algorithm

quicksort