快速排序越界或循环

Question

我目前正在尝试在java中实现快速排序，当我运行程序时，我要么得到一个超出数组长度范围的索引，要么得到一个无限循环，不要问我怎么做。此外，交换本身，当它起作用时，是不正确的，所以是的。

public class Quicksort {

   /*
    * Entry method for Quicksort
    */
   public static void quicksort(int[] a) {
      quicksort(a, 0, a.length-1);
   }

   /*
    * Quicksort! 
    * Operates in-place, i.e. it doesn't create a copy.
    */  
   public static void quicksort(int[] a, int from, int to) {
      // Base case: Sorting range is 1 element or empty.
      if(from >= to){
         return;
      }
      // TODO
      else{
         
         
         
         int ipivot = from; // Pivot p
         System.out.println("Pivot p = " + a[ipivot]);
         printArray(a);
         
         // Split the array in two ranges: Left are the elements <=p and right >p.
         // Do this by swapping the elements that don't belong in the given range. 
         // If i and j cross, swapping is finished.
         int i = ipivot+1;
         int j = to;
         while (i<j) {
            // Look for an element <=p right-hand side 
            while(j>= 0 &&a[j]>a[ipivot]){
               j--;
            }
            
            
            // Look for an element >p left-hand side 
            while(i< a.length && a[i]<a[ipivot]){
               i++;
            }
            
            
            // Swap the elements, but only if pointers aren't crossed.
            if (i<j) {
               swap(a, i, j);
            } 
            else {
               break;
            }
 
               
         }
         // The pivot can now be moved to its final position at i.
         // NOTE: Check if pivot needs to be moved BEFORE i.
         int ipivot_final =i;
         System.out.println("swapping " + a[ipivot] +" @"+ipivot+" and " + a[ipivot_final]+" @"+ipivot_final + " (pivot)");
         swap(a, ipivot, ipivot_final);
         
         printArray(a);
         System.out.println();
         
         // Recursion case: Sort left and right range of pivot recursively.
         quicksort(a, from, ipivot_final-1);
         quicksort(a, ipivot_final+1, to);
      }
   }
   /*
    * HELPER METHODS
    */
   public static void printArray(int[] a) {
      for (int i=0; i<a.length; i++) {
         System.out.print(a[i] + ", ");
      }
      System.out.println();
   }

   public static boolean isSorted( int[] array ) {
      for ( int j=0; j<array.length-1; j++ ) {
         if (array[j] > array[j+1])
            return false;      
      }
      return true;
   }

   private static int[] createRandomArray(int size, int minVal, int maxVal) {
      int[] a = new int[size];
      for (int i=0; i<a.length; i++) {
         a[i] = (int) (Math.random()*(maxVal-minVal) + minVal);
      }
      return a;
   }

   private static void swap(int[] a, int i, int j) {
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
   }
   
   
   /*
    * MAIN
    */

   public static void main(String[] args) {
      final int MINSIZE = 10;
      final int MAXSIZE = 10;
      for (int size = MINSIZE; size <= MAXSIZE; size++) {
         int[] a = createRandomArray(size, 0, size);
         System.out.println("Unsorted array of size "+a.length);
         printArray(a);
         System.out.println("\nRunning Quicksort ...");
         quicksort(a);
         System.out.println("\nSorted array:");
         printArray(a);
         assert isSorted(a) : "Array is not sorted!";
         if (isSorted(a))
            System.out.println("\n\nSuccess!!\n\n");
         else
            System.out.println("\n\nERROR !! Something went wrong.\n\n");
      }
   }

}

我尝试过更改条件的顺序以及条件本身

Answer 1

这些循环中的条件是错误的：

            while(j>= 0 &&a[j]>a[ipivot]){
               j--;
            }
            
            
            // Look for an element >p left-hand side 
            while(i< a.length && a[i]<a[ipivot]){
               i++;
            }

不允许

j

低于

from

，并且不允许

i

高于

to

。或者，您可以在

i

和

j

交叉时立即中断循环：

            while (j >= i && a[j] > a[ipivot]) {
               j--;
            }
            
            
            // Look for an element >p left-hand side 
            while (i <= j && a[i] < a[ipivot]) {
               i++;
            }

此评论不正确：

         // The pivot can now be moved to its final position at i.

枢轴的最终位置不是

i

，而是

i-1

。也可以拼写为

j

，因为一旦

i

和

j

交叉，循环就会终止。

了解这一点的一种方法是考虑极端情况，即主元元素恰好是子数组中最少的元素。那么

i

永远不会从其初始值

ipivot + 1

开始递增，但枢轴元素的正确索引是其初始值

ipivot

。

另请注意，如果您允许

i

一直增加到

a.length

，那么此时评估

a[i]

将产生

IndexOutOfBoundsException

。这也与以下事实有关：在分区循环结束时，左侧分区的顶部索引是

i - 1

，而不是

i

。

Answer 2

这是一个实现，使用 Wikipedia 文章中的算法。
维基百科 – 快速排序 – Lomuto 分区方案。

评论来自原文。

// Sorts a (portion of an) array, divides it into partitions, then sorts those
void quicksort(int[] A, int lo, int hi) {
    // Ensure indices are in correct order
    if (lo >= hi || lo < 0) return;

    // Partition array and get the pivot index
    int p = partition(A, lo, hi);

    // Sort the two partitions
    quicksort(A, lo, p - 1); // Left side of pivot
    quicksort(A, p + 1, hi); // Right side of pivot
}

// Divides array into two partitions
int partition(int[] A, int lo, int hi) {
    int pivot = A[hi]; // Choose the last element as the pivot

    // Temporary pivot index
    int i = lo - 1, t;

    for (int j = lo; j <= hi - 1 ; j++) {
        // If the current element is less than or equal to the pivot
        if (A[j] <= pivot) {
            // Move the temporary pivot index forward
            i = i + 1;
            // Swap the current element with the element at the temporary pivot index
            t = A[i];
            A[i] = A[j];
            A[j] = t;
        }
    }

    // Move the pivot element to the correct pivot position (between the smaller and larger elements)
    i = i + 1;
    t = A[i];
    A[i] = A[hi];
    A[hi] = t;
    return i; // the pivot index
}