Quicksort(摘自《Programming perls》一书)

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

快速排序类：

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: %dn",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: %snn",Arrays.toString(intArray));
     System.out.printf("Size of Array is: %dn",intArray.length);
     QuickSort qs = new QuickSort();
     int[] A = qs.QSort(intArray, 5, intArray.length);
     System.out.println(Arrays.toString(intArray));
 }

}

好吧，直到现在为止。代码编译，除了排序算法之外的所有内容都是错误的。我试图从逻辑上理解QuickSort算法中发生的事情，并使用Programming Perls一书来帮助我理解。

以下是我的问题列表：

根据书中，在 for 循环中的 QuickSort 类中，"i's"条件子句需要是"i <=U"，但如果我这样做，代码会给我一个"数组索引越界"错误。为什么会这样？我知道什么是"数组索引越界"错误，我只是无法理解为什么数组位置不存在？
第一个 if 子句检查数组是否排序。当我编译代码时，此子句在第一次尝试时就满足（这首先不应该发生）。如果是，为什么函数不通过返回 A 行结束？

我正在使用的书是约翰·本特利（John Bentley）的，第112页。

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

您的问题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/

在你调用QSort时，上限是排他性的

QSort(A, L, M-1 );

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

它应该是

QSort (A, L, M);

以及@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: %snn",
                            Arrays.toString(intArray));
        System.out.printf("Size of Array is: %dn", intArray.length);
        QSort.sort (intArray, 0, intArray.length);
        System.out.println(Arrays.toString(intArray));
    }
}

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

你应该得到一个介于 L 和 U 之间的随机整数，方法是使用：

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

另外，如果您希望自己成为数组中最大的索引，请将其传递给intArray.length - 1

相关内容

最新更新

热门标签：