Hoare的分区无法正常工作（快速排序）

Question

因此，遵循Cormen的quicksort和hoares分区算法之后，这就是我能够生成的代码。数组出来的部分内容是未初始化的元素/垃圾元素，我一辈子都无法弄清楚为什么……我以为我完全按照书中的描述遵循算法。

这是本书中的伪代码：

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

这是我将其翻译成的C ++代码：

void quickSort(int arr[], int p, int r){
    if(p < r){
        int q = hoare_partition(arr, p, r);
        quickSort(arr, p, q-1);
        quickSort(arr, q+1, r);
    }
}

int hoare_partition(int arr[], int p, int r){
    int x = arr[p];
    int i = p - 1;
    int j = r + 1;
    while(true){
        do{
            j--;
        }while(arr[j] > x);
        do{
            i++;
        }while(arr[i] < x);
        if(i < j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        else 
            return j;
    }
}

我正在使用以下内容进行测试

cout << endl << endl << "Testing quicksort" << endl;
int tarr[10] = {2, 30, 1, 99, 46, 33, 48, 67, 23, 76};
quickSort(tarr, 0, 10);
cout << "arr after quicksort: ";
for(int i = 0; i < 10; i++){
    cout <<  tarr[i] << " ";
}
cout << endl;

输出

arr after quicksort: -2146162183 1 2 23 30 33 46 48 67 76

任何帮助将不胜感激...感谢

编辑

将测试用例调用更改为quickSort（arr，0，9）可以解决这种情况。

但是，使用反向排序的数组作为输入，这是输出：

arr2 is:
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
arr2 after quicksort :
1 3 5 7 9 11 13 15 17 19 20 21 18 22 16 23 14 24 12 25 10 26 8 27 6 28 4 29 2 30

使用以下测试代码：

int arr2[30];
fillArrayReverse(arr2, 30);
cout << "arr2 is :" << endl;
for(int i = 0; i < 30; i++){
    cout << arr2[i] << " ";
}
cout << endl;
quickSort(arr2, 0, 29);
cout << "arr2 after quicksort: " << endl;
for(int i = 0; i < 30; i++){
    cout << arr2[i] << " ";
}
cout << endl;

Answer 1

书中的伪代码是正确的。问题不是j返回的（这是正确的），而是quickSort函数本身。它实际上应如下所示：

void quickSort( int arr[], int p, int r )
{
    if( p < r )
    {
        int q = hoare_partition( arr, p, r );
        quickSort( arr, p, q );
        quickSort( arr, q + 1, r );
    }
}

请注意，我们q - 1在第一个调用中将删除quickSort，并将其替换为just q。之前，我们实质上是跳过枢轴点，而仅对其周围的项目进行排序。在快速浏览了Wikipedia上的Hoard Partition伪代码后，我注意到了这种差异。