所以下面从Cormen的快速排序和hoares分区算法之后，这是code，我是能够生产。该阵列出来的部分排序与未初始化的元素/垃圾的元素，我不能为我的生命弄清楚为什么...我想我也跟着算法完全按照书中写的。

下面是书中的伪code直：

  HOARE分区（A，P，R）
1×= A [P]
2我= P  -  1
3 J = R + 1
4，而TRUE
5重复
6当J = J  -  1
7，直到[J] LT = X
8重复
9 I = I + 1
10至A [1]＆GT; = X
11，如果我＆LT; Ĵ
12交换A [I]与A [J]。
13其他复位J
 

这里是C ++ code我翻译成：

 无效快速排序（INT改编[]，INT磷，INT读）{
    如果（P＆所述; r）的{
        INT Q = hoare_partition（ARR，P，R）;
        快速排序（ARR，P，Q-1）;
        快速排序（ARR，Q + 1，R）;
    }
}

INT hoare_partition（INT改编[]，INT磷，INT读）{
    INT X = ARR [P]。
    INT I = P  -  1;
    INT J = R + 1;
    而（真）{
        做{
            j--;
        }而（ARR [J] GT; X）;
        做{
            我++;
        }而（改编[1]  - ; x）的;
        如果（ⅰ＆所述; j）条{
            INT TEMP =改编[I]
            改编[i] = ARR [J]。
            ARR [J] =温度;
        }
        其他
            复位J;
    }
}
 

即时通讯使用以下测试它

  COUT＆LT;＆LT; ENDL＆LT;＆LT; ENDL＆LT;＆LT; 测试快速排序＆LT;＆LT; ENDL;
INT塔尔[10] = {2，30，1，99，46，33，48，67，23，76};
快速排序（塔尔，0，10）;
COUT＆LT;＆LT; 常用3快速排序后：;
的for（int i = 0;我小于10;我++）{
    COUT＆LT;＆LT;塔尔[1]  - ;＆其中; ;
}
COUT＆LT;＆LT; ENDL;
 

输出

 改编后的快速排序：-2146162183 1 2 23 30 33 46 48 67 76
 

任何帮助是AP preciated提前...谢谢

修改

更改测试案例调用快速排序（ARR，0，9）固定它的这种局面。

然而，与逆转录有序数组作为输入，这是输出：

  ARR2是：
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快速排序后：
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
 

使用这个测试code：

  INT ARR2 [30];
fillArrayReverse（ARR2，30）;
COUT＆LT;＆LT; ARR2是：＆LT;＆LT; ENDL;
的for（int i = 0;我小于30;我++）{
    COUT＆LT;＆LT; ARR2 [1]  - ;＆其中; ;
}
COUT＆LT;＆LT; ENDL;
快速排序（ARR2，0，29）;
COUT＆LT;＆LT; 后快速排序ARR2：＆其中;＆其中; ENDL;
的for（int i = 0;我小于30;我++）{
    COUT＆LT;＆LT; ARR2 [1]  - ;＆其中; ;
}
COUT＆LT;＆LT; ENDL;
 

解决方案

这是一个与你的测试code的一个问题。第三个参数应该是最后一个元素的索引，而不是元素数：

 快速排序（塔尔，0,9）;
 

您正在阅读过去的数组的末尾。

有关霍尔分区，快速排序和Cormen等详细信息，请参阅这个问题。

为您遇到的其他问题最​​简单的解决方法是改变hoare_partition（），以回我，而不是第j。见链接查看更多细节（这是在这本书据说是错误）。

So after following the quicksort and hoares partition algorithm from Cormen, this is the code that I was able to produce. The array comes out partly sorted with uninitialized elements/garbage elements and I can't for the life of me figure out why... I thought I followed the algorithm exactly as the book writes it.

Here is the pseudocode straight from the book:

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

And here is the C++ code I translated it into:

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;
    }
}

Im using the following to test it

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;

The output

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

Any help is appreciated ahead of time...thanks

EDIT

Changing the test case call to quickSort(arr, 0, 9) fixed it for this situation.

However, with a reverse sorted array as the input this is the output:

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

using this test code:

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;

It's a problem with your test code. The third parameter should be the index of the last element, not the number of elements:

quickSort(tarr, 0, 9);

You're reading past the end of the array.

For more information about Hoare partitioning, Quicksort and Cormen etc, see this question.

The simple fix for the other problems you're having is to change hoare_partition() to return i instead of j. See the link for more details (it's an error in the book reportedly).