c++ - Hoare分区不起作用？

我一直在尝试实现Hoare分区方法，但是我和计算机似乎都无法理解它，因为它是用Cormen和Wikipedia编写的。
两种来源中的算法如下：

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，所以我将成为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;
}

最佳答案

您需要使用正确的quicksort例程，因为Hoare将数组分为左部分和右部分，而Lomuto不像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]

也许您正在寻找的是快速选择来找到第k个元素，其中k =数组大小/2。这类似于快速排序，但是它仅以递归方式搜索包含第k个元素的数组的左侧或右侧部分。维基文章：

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