c++ - 霍尔分区不起作用？

Question

我一直在尝试实现 Hoare 分区方法，但我和计算机似乎都无法理解它，因为它是用 Cormen 和维基百科编写的。两个来源中的算法如下所示:

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            j := j - 1
        while A[j] > pivot
        do
            i := i + 1
        while A[i] < pivot
        if i < j then
            swap A[i] with A[j]
        else
            return j

对于以下数组: 9 3 11 55 4 ，在用上述函数对其进行分区后，它将如下所示: 4 3 11 55 9 并且主元索引将为 2，这是完全错误的。首先，9 和 4 将被交换，因此 i 将变为 2，j 将变为 4。但是，在下一次迭代中，由于 do while 循环，9 将被跳过并且永远不会再次交换。我的想法有问题吗？ (我认为我在C++中的实现没有任何错误)

#include <iostream>
using namespace std;
int a[100];
int partitie(int st, int dr){
    int i,j,x;
    x=a[st];
    i=st-1;
    j=dr+1;
    while(true){
        do{
            j--;
        }while(a[j]>x);
        do{
            i++;
        }while(a[i]<x);
        if(i<j) swap(a[i],a[j]);
        else return j;
    }
}
int main() {
    int i,n;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    cout<<partitie(1,n)<<endl;
    for(i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}

Answer 1

您需要使用正确的快速排序例程，因为 Hoare 将数组拆分为左侧部分和右侧部分，这与将数组拆分为左侧部分、主元和右侧部分的 Lomuto 不同。

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)        // not quicksort(A, lo, p-1)
        quicksort(A, p + 1, hi)

同样在中间选择一个枢轴意味着已经排序或反向排序的数组被快速排序，而不是最坏的情况:

    pivot := A[lo+(hi-lo)/2]  // or := A[(lo+hi)/2] if overflow not an issue

仍然会有最坏的情况模式，但至少处理了简单的模式。 3 的中位数有点慢，但减少了最坏情况模式的数量:

    md = lo + (hi-lo)/2
    if (A[lo] > A[hi])
        swap(A[lo], A[hi])
    if (A[lo] > A[md])
        swap(A[lo], A[md])
    if (A[md] > A[hi])
        swap(A[md], A[hi])
    pivot := a[md]

也许你要找的是quick select找到第k个元素，其中k = array size/2。它类似于quick sort，但它只是递归地搜索包含第k个元素的数组的左侧或右侧部分.维基文章:

http://en.wikipedia.org/wiki/Quickselect