2

我已经编写了这段代码，但它会在控制台中打印这些堆栈跟踪，请帮助我，谢谢！（“p”和“q”分别是我们数组的第一个和最后一个索引）

public class JavaQuickSort {

public static void QuickSort(int A[], int p, int q) {
    int i, last = 0;

    Random rand = new Random();
    if (q < 1) {
        return;
    }
    **swap(A, p, rand.nextInt() % (q+1));**

    for (i = p + 1; i <= q; i++) {
        if (A[i] < A[p]) {
            swap(A, ++last, i);
        }

    }
    swap(A, p, last);
    QuickSort(A, p, last - 1);
    QuickSort(A, last + 1, q);
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    **A[i] = A[j];**
    A[j] = temp;


}
public static void main(String[] args){
    int[] A = {2,5,7,3,9,0,1,6,8};
    **QuickSort(A, 0,8 );**
    System.out.println(Arrays.toString(A));
}
}

堆栈跟踪：

run:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -3
        at JavaQuickSort.swap(JavaQuickSort.java:38)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:22)
        at JavaQuickSort.main(JavaQuickSort.java:45)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)

我还将导致这些堆栈跟踪的那些语句加粗。喜欢 ==> ** ...**

编辑：

public class JavaQuickSort {

public static void QuickSort(int arr[],int lo,int hi) {
    int n = arr.length;
    if(n<=1)
        return;
    **int r = partition(arr);**
    **QuickSort(arr,lo , r-1);**
    QuickSort(arr, r+1, hi);
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    **A[i] = A[j];**
    A[j] = temp;


}
public static int partition(int arr[]){
      int i, last = 0;
 Random rand = new Random();
    int n = arr.length;
    if (n <= 1)
        return arr[0];

    **swap(arr, 0, rand.nextInt(n));**

    for (i =1; i <n; i++) {
        if (arr[i] < arr[0]) {
            swap(arr, ++last, i);
        }

    }
    swap(arr, 0, last);
    return last;
}
public static void main(String[] args){
    int[] A = {2,5,7,3,9,0,1,6,8};
    **QuickSort(A, 0,8 );**
    System.out.println(Arrays.toString(A));
}
}

为了更容易理解，我编辑了我的帖子，它还将打印这些堆栈跟踪，并且我将导致这些堆栈跟踪的行加粗！！！

堆栈跟踪：

run:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
        at JavaQuickSort.swap(JavaQuickSort.java:27)
        at JavaQuickSort.partition(JavaQuickSort.java:39)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:19)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.main(JavaQuickSort.java:52)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)

请帮帮我谢谢

编辑：

我已经写了这段代码，注意这篇文章的第一答案，但它不会对我的数组进行排序！！！

public class JavaQuickSort {

public static void QuickSort(int arr[], int lo, int hi) {
    if (hi > lo) {
         Random rand = new Random();
        int pivotIndex = lo + rand.nextInt(hi-lo+1);
        int pivotnewIndex = partition(arr, lo, hi,pivotIndex);
        QuickSort(arr, lo, pivotnewIndex - 1);
        QuickSort(arr, pivotnewIndex + 1, hi);
    }
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    A[i] = A[j];
    A[j] = temp;


}

public static int partition(int arr[],int lo,int hi,int pivotIndex)
{
    int pivotValue = arr[pivotIndex];
    swap(arr, hi, pivotIndex);
    int storeIndex = lo;
    for(int i = lo;i<hi;i++){
        if (arr[i]<=pivotValue)
        swap(arr, storeIndex, i);
        storeIndex = storeIndex ++;
    }
    swap(arr, storeIndex, hi);
    return storeIndex;

}

public static void main(String[] args) {
    int[] A = {2, 5, 7, 3, 9, 0, 1, 6, 8};
    QuickSort(A, 0, 8);
    System.out.println(Arrays.toString(A));
}
}

输出：

run:
[2, 9, 3, 8, 0, 6, 7, 1, 5]
BUILD SUCCESSFUL (total time: 2 seconds)

我需要你的帮助我真的很困惑！

4

4 回答 4

3

您的代码的一些问题是：

  • 不要Random为一次性使用创建新实例。只需创建一次，将其存储在一个static字段中，然后使用它为您的应用程序生成许多随机数。
  • 为枢轴创建随机索引时，它必须介于两者p之间q。
  • 使用Random.nextInt(int n)重载生成给定范围内的随机数
  • 也许使用loandhi而不是pand q, 而int[] arr不是int A[]
  • .length您可以使用其成员获取数组的长度

至于快速排序算法本身，它看起来不像我以前见过的任何东西。我建议研究标准的命令式实现并对其进行调整。

也可以看看

更新

不幸的是，您在某种程度上混淆了 Wikipedia 中的伪代码。你想调整这个算法：

  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i  from  left to right - 1 // left ≤ i < right  
         if array[i] ≤ pivotValue 
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

  procedure quicksort(array, left, right)
     if right > left
         select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex - 1)
         quicksort(array, pivotNewIndex + 1, right)

请注意，上述算法选择子数组的中间元素介于left和right作为枢轴索引。既然你想要一个随机的快速排序，你想选择一个介于left和之间的随机索引right，所以公式需要更改如下：

  pivotIndex := left + (random number between 0 and right-left inclusive)

因此，例如，如果left = 5和right = 7，那么您想pivotIndex成为介于和5 + x之间的随机数。x07-5=2

由于Random.nextInt(n)具有排他性上限，因此将其转换为 Java 将类似于：

int pivotIndex = lo + rand.nextInt(hi - lo + 1);

最终修正

您在这里为初学者犯了一个常见的错误：

    // HORRIBLE FORMATTING! Don't do this!
    if (arr[i]<=pivotValue)
    swap(arr, storeIndex, i);
    storeIndex = storeIndex ++;

如果您注意到上面的伪代码，这两个语句都应该是if主体的一部分，但是上面的代码，当正确缩进并添加大括号时，实际上是这样的：

    // PROPER FORMATTING! Reveals bug instantly!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex, i);
    }
    storeIndex = storeIndex ++;

因此，解决方法是将storeIndex增量移动到if主体，如下所示：

    // Corrected according to pseudocode!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex, i);
        storeIndex = storeIndex ++;
    }

或者你也可以这样做：

    // Nice and clear!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex++, i);
    }

这次最新更新的教训是：

  • 始终正确缩进代码
    • 一个好的IDE可以让这变得轻而易举，你真的没有借口
  • 养成在if语句上加上大括号的习惯，即使它们不是绝对必要的
    • 许多细微的错误是由于省略了大括号
  • 明智地使用后/前增量
    • 像许多事情一样，它们可能会被滥用到无法理解的程度，但如果使用得当且惯用的话，它们会产生简洁易读的代码

最后一件事

当我提到.length数组时，我的意思不是这个：

int[] A = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(A, 0, 8); // BAD! Don't hardcode array length!

你应该做这个：

int[] arr = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(arr, 0, arr.length - 1); // GOOD!
于 2010-06-08T07:51:41.483 回答
0

随机发生器产生正值和负值。这就是为什么最终你用负值调用交换q。

于 2010-06-08T07:53:10.743 回答
0 
swap(A, p, rand.nextInt() % (q+1));

生成的随机整数可能低于 p，显然您希望它介于 p 和 q 之间。

于 2010-06-08T07:54:01.857 回答
0

由于这不是家庭作业，我会将家庭作业类别包括自学，您应该只使用标准Arrays.sort(int[]).

于 2010-06-09T07:00:23.460 回答