QuickSort Hoare 的分区不起作用

Question

您好，我已经尝试编写 Hoare 的分区函数大约 5 个小时了。我读了 this and 甚至直接从这些问题中复制了 "correct" 函数，但它仍然离答案很远。这是我从 Cormen 的书中得到的 "translated" 代码。

int Hpartition(int A[], int p, int r){
int x = A[p];
int i = p - 1;
int j = r + 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;
 }
}

快速排序：

void qs(int A[],int p,int r){
if(p<r){
    int q=Hpartition(A,p,r);
    qs(A,p,q-1);
    qs(A,q+1,r);
}
}

主要：

int main(int argc, const char * argv[]) {
int tab[10];

for(int k=0;k<10;k++){
    cin >> tab[k];
}


qs(tab,0,9);

for(int i=0;i<10;i++){
    cout << tab[i] << " ";
}
return 0;
}

对于此数据：

2 4 1 3 5 7 6 8 10 9

它产生这个结果：

2 4 9 3 5 7 6 8 10 1

根据之前关于该主题的问题，我知道本书中可能存在一些错误。但即使我应用了前面问题的答案，它也不起作用。

这是书中的算法：

HOARE-PARTITION(A, p, r)
1 x = A[p]
2 i = p - 1
3 j = r + 1
4 while TRUE
5     repeat
6        j = j - 1
7     until A[j] <= x
8     repeat
9        i = i + 1
10    until A[i] >= x
11    if i < j
12        exchange A[i] with A[j]
13    else return j

在此先感谢您的帮助。

Answer 1

您在翻译书中的代码时遇到 2 个错误：

do{
     j--;
  }while(A[j] <= x);

你应该反转这个：

do{
     j--;
  }while(A[j] > x);

同：

do{
     i++;
  }while(A[i] >= x);

这里还有一个：

qs(A,p,q-1);
qs(A,q+1,r);

更改为：

qs(A,p,q);
qs(A,q+1,r);

QuickSort Hoare 的分区不起作用

QuickSort Hoare's partitioning not working

sorting

quicksort

partition