霍尔分区无法正常工作（快速排序）

Question

所以在遵循 Cormen 的快速排序和 hoares 分区算法之后，这就是我能够生成的代码。该数组部分用未初始化的 elements/garbage 元素排序，我终其一生都无法弄清楚为什么……我以为我完全按照书中所写的算法进行了操作。

这里是直接来自书本的伪代码：

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

你的测试代码有问题。第三个参数应该是最后一个元素的索引，不是元素个数：

quickSort(tarr, 0, 9);

您正在阅读数组末尾。

有关 Hoare 分区、Quicksort 和 Cormen 等的更多信息，请参阅 this question。

解决您遇到的其他问题的简单方法是将 hoare_partition() 更改为 return i 而不是 j。有关详细信息，请参阅 link（据报道这是书中的一个错误）。

Answer 2

书中的伪代码是正确的。问题不在于 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 );
    }
}

请注意，我们在第一次调用 quickSort 时删除了 q - 1，并仅将其替换为 q。之前我们基本上跳过了枢轴点，只围绕它排序项目。在查看关于 wikipedia.

快速排序的 Hoare Partition 伪代码后，我注意到了这种差异

霍尔分区无法正常工作（快速排序）

Hoare's partition not working correctly (quicksort)

c++

algorithm

quicksort

编辑