0

我正在努力学习有关排序算法的所有知识。今天的议程是快速排序。这是我得到的。

快速排序类：

import java.util.*;

  public class QuickSort{
    public static void swap(int A[], int x ,int y){
      int temp = A[x];
      A[x] = A[y];
      A[y] = temp;
    }

     public static int[] QSort(int A[], int L, int U){
       Random randomGenerator = new Random();

       if (L >= U){
         System.out.printf("The value of L: %d, U: %d\n",L,U);
         return A; // Sorted.

       }

       if (L < U ){
         int randomInt = randomGenerator.nextInt(U);
         swap( A, L, randomInt);
         int T = A[L];
         int M = L;

       for (int i = L+1;i < U; i++){
         if ( A[i] < T){
           M = M+1;
           swap(A, M, i);
         }
       }
       swap(A, L, M);
       QSort(A, L, M-1 );
       QSort(A, M+1, U );
    }

     //System.out.println(Arrays.toString(A));
     return A;
   }

 }

主要的：

 import java.util.*;

 public class Main{
   public static void main(String [] args){

     int[] intArray =  {1,3,2,4,56,0,4,2,4,7,80,120,99,9,10,67};

     System.out.printf("Original Array was: %s\n\n",Arrays.toString(intArray));

     System.out.printf("Size of Array is: %d\n",intArray.length);
     QuickSort qs = new QuickSort();
     int[] A = qs.QSort(intArray, 5, intArray.length);
     System.out.println(Arrays.toString(intArray));
 }

}

嗯，到现在为止。代码可以编译，除了排序算法之外的一切都是错误的。我试图从逻辑上理解 QuickSort 算法中发生的事情，并使用 Programming Perls 这本书来帮助我理解。

这是我的问题列表：

  1. 根据本书，在 for 循环中的 QuickSort 类中，“i's”条件子句必须是“i <=U”，但如果我这样做，代码会给我一个“数组索引超出范围”错误。为什么会这样？我知道“数组索引越界”错误是什么，我只是不明白为什么数组位置不存在？

  2. 第一个 if 子句检查数组是否已排序。当我编译代码时，这个子句在第一次尝试时就遇到了（这不应该首先发生）。如果是，为什么函数不通过 return A 行结束？

我正在使用的书是 John Bentley 的第 112 页。

4

3 回答 3

1

在您调用QSort上限时是排他的

QSort(A, L, M-1 );

但是在这里您错过了对 index 处的数字进行排序M-1。

它应该是

QSort (A, L, M);

PS。以及@LeeNeverGup 对随机数的评价。

基本上，这是：

import java.util.*;

public class QSort {
    public static void swap(int A[], int x, int y) {
        int temp = A[x];
        A[x] = A[y];
        A[y] = temp;
    }

    public static void sort (int A[], int L, int U) {
        Random randomGenerator = new Random();

        if (L + 1 >= U)
            return;

        int randomInt = L + randomGenerator.nextInt(U - L);
        swap(A, L, randomInt);
        int T = A[L];
        int M = L;

        for (int i = L + 1; i < U; i++) {
            if (A[i] < T) {
                M = M + 1;
                swap(A, M, i);
            }
        }
        swap(A, L, M);
        sort(A, L, M);
        sort(A, M + 1, U);
    }

    public static void main(String[] args) {

        int[] intArray =
            { 1, 3, 2, 4, 56, 0, 4, 2, 4, 7, 80, 120, 99, 9, 10, 67 };

        System.out.printf(  "Original Array was: %s\n\n",
                            Arrays.toString(intArray));

        System.out.printf("Size of Array is: %d\n", intArray.length);
        QSort.sort (intArray, 0, intArray.length);
        System.out.println(Arrays.toString(intArray));
    }
}
于 2013-11-01T09:41:47.937 回答
1

除了已经指出的其他异常情况外，

您的问题 1：
如前所述， U 的初始值应该是intArray.length - 1。

int[] A = qs.QSort(intArray, 5, intArray.length - 1 );

您的问题 2：
第一个 if 子句不检查数组是否已排序，它只是检查 U 和 L 指针是否相互交叉。

对于快速排序，这意味着对于当前枢轴，所有小于枢轴的项目都在其左侧，所有大于枢轴的元素都在其右侧。

这种交叉可能在排序过程中发生多次，具体取决于完全排序数组所需的枢轴更改次数。

有关快速排序的更多信息，以下链接可能会有所帮助。http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/

于 2013-11-01T08:49:35.573 回答
0

在这一行：int randomInt = randomGenerator.nextInt(U);

您应该使用以下方法获得 L 和 U 之间的随机整数：

int randomInt = L + randomGenerator.nextInt(U - L);

此外，如果您希望 U 成为数组中的最大索引，则应该传递给它intArray.length - 1

于 2013-11-01T08:42:15.487 回答