c++ - 部分排序的快速排序

Question

我想将快速排序修改为只对顶部中值项进行排序的位置。所以这样的集合 [9 5 7 1 2 4 6]，其中 5 是中位数，部分排序的集合类似于 [1 2 4 5 9 6 7]。

template <class Comparable>
void objectSwap(Comparable &lhs, Comparable &rhs) {
    Comparable tmp = lhs;
    lhs = rhs;
    rhs = tmp;
}

template <class Comparable>
void choosePivot(vector<Comparable> &a, int first, int last) {
    int middle = (first + last) / 2;
    objectSwap(a[first], a[middle]);
}

template <class Comparable>
void partition(vector<Comparable> &a, int first, int last, int &pivotIndex) {
    // place the pivot in a[first]
    choosePivot(a, first, last);
    Comparable pivot = a[first];
    int lastS1 = first;
    int firstUnknown = first + 1;

    for (; firstUnknown <= last; ++firstUnknown) {
        if (a[firstUnknown] < pivot) {
            ++lastS1;
            objectSwap(a[firstUnknown], a[lastS1]);
        }
        // else item from unknown belongs in S2
    }
    // decide a new pivot
    objectSwap(a[first], a[lastS1]);
    pivotIndex = lastS1;
}

template <class Comparable>
void partialsort(vector<Comparable> &a, int first, int last) {
    int pivotIndex;

    if (first < last) {  
        partition(a, first, last, pivotIndex);
        partialsort(a, first, pivotIndex - 1);
        partialsort(a, pivotIndex + 1, last);
    }
}

template <class Comparable>
void partialsort(vector<Comparable> &a) {
    partialsort(a, 0, a.size() - 1);
}

我一直在观看 mycodeschool 在 youtube 上对快速排序的分析(让我知道任何其他好的视频，如果你知道的话!)，我很确定我只需要更改 partialsort(vector, int , int) 方法。
我的第一 react 是把它想象成合并排序，取一个空数组，并在长度/2 被填充后停止算法。但我知道这不是快速排序的工作方式。所有的递归调用以及 first、last 和 pivot 总是变化的方式，让我很难跟踪正在发生的事情。我也不确定我怎么知道我什么时候有中位数。这是一个家庭作业问题，所以如果有人知道我应该如何处理这个问题或可以帮助我更好地理解快速排序的资源，我将不胜感激。仅仅知道如何改变它对我更好地理解算法没有多大帮助。
对不起，如果听起来我有权获得我想要的帮助!

Answer 1

这是一个分而治之的算法，所以你可以跳过任何完全在数组中间位置后面的分区，一旦前半部分排序后，它自然会保持中值。