0

我正在从我的数据结构和算法书籍中进行快速排序。在书中，它列出了一个快速排序方法，然后是一个它希望您与快速排序一起使用的 hoare 分区。我似乎遇到了一个问题，即我的 hoare 分区在数组上使用了超出范围的数字。它要么使用 8，要么如果我尝试修复它，它会变为 -1。我是否将书籍伪正确地转换为java？

快速排序伪代码

QuickSort(A, p, r)
if p<r
    q = partition(A, p, r);
    QuickSort(A, p, q - 1);
    QuickSort(A, q, r);

霍尔分区伪代码

Hoare-Partition(A,p,r)
    x= A[p]
    i = p-1
    j=r+1
    while true
        repeat
            j=j-1
        until A [j] <= x
        repeat
            i = i +1
        until A[i] >= x
        if i < l
           exchange A[i] with A[j]
        else return j

我的代码

public class RunSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] sortNumbers = {4,5,6,2,3,7,2,1};
        int[] sorted = new int[sortNumbers.length];

        sorted = QuickSort(sortNumbers, 1, sortNumbers.length);
        System.out.print(sorted);
    }

    public static int[] QuickSort(int[] A, int p, int r){
        if(p < r){
            int q = partition(A, p, r);
            QuickSort(A, p, q - 1);
            QuickSort(A, q, r);
        }
        return A;

    }

    public static int partition(int[] A, int p, int r){
        int x = A[p];
        int i = p - 1;
        int j = r + 1;
        int temp;

        while(true){
            while(A[j] <= x && j != 0){
                j--;
            }
            while(A[i] >= x && i != A.length){
                i++;
            }
            if(i < j){
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }else{
                return j;
            }
        }
    }
}
4

2 回答 2

2

提示：repeat {...} until (condition)不做与while (condition) {...}.

于 2013-02-28T15:59:34.777 回答
0

根据文本，伪代码通常使用 1..arrayLength 作为数组的索引边界，但在 Java 等中，它是 0..arrayLength-1。您需要将参数调整为 in 中的主QuickSort调用main。

(As a nitpick, QuickSort should start with a lowercase letter by convention.)

于 2013-02-28T16:08:00.160 回答