快速排序算法

对于快速排序过程中一个的问题：为什么在qsort中递归时，需要将递归范围改为[lo, pos-1]而不是[lo, pos]?

以下看一个具体例子：

#include <iostream>

using namespace std;

int partition(vector<int> &arr, int lo, int hi) {
    int i = lo - 1;
    int key = arr[hi];
    for (int j = lo; j < hi; ++j) {
        if (arr[j] <= key) {
            ++i;
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    arr[hi] = arr[i + 1];
    arr[i + 1] = key;
    return i + 1;
}

void qsort(vector<int> &arr, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int pos = partition(arr, lo, hi);   // 这里返回了pos=5,所以出现了递归调用，而且这个递归调用和之前的调用一模一样
    qsort(arr, lo, pos - 1);
    qsort(arr, pos + 1, hi);
}

int main() {
    vector<int> arr{12, 34, 11, 46, 12, 89};
    qsort(arr, 0, arr.size() - 1);
    for (auto c:arr) {
        cout << c << " ";
    }
    cout << endl;

    return 0;
}

在归并排序过程中，递归的两个子范围为[lo, mid]和[mid+1, hi]。那是因为[lo, mid]区间必然是[lo, hi]区间的子区间，而不会和区间[lo, hi]重叠。而这里的pos是通过partition函数返回的，表示在数组中小于等于key的元素范围，pos有可能等于hi,这时区间[lo, pos]和区间[lo, hi]重叠，便会造成无法终止的递归调用。

但实际上，在快速排序的过程中，每次我们至少可以确定一个元素的位置，即主元的位置，因此，问题的规模会慢慢变小。