QuickSort算法的StackOverFlow錯誤

Question

我得到此代碼的StackOverflowError。它說184/185行，這是我初始化分割位置（見下面）並調用第一個遞歸quickSort方法的地方。我可以看到代碼在遞歸中退出時遇到了麻煩，但我不確定發生了什麼。每次我打電話給quickSort時，它都在一個較小的分區上。

import java.util.*; 

public class java2{ 

public static int MAXINT = 10000; 
public static int[] intArray = new int[MAXINT]; 
public static int index; 
public static long comparisons; 

public static void main(String[] args) 
{  
    System.out.println("SORTING ALGORITHM: Quicksort"); 
    // Create a random array of integers and sort using the CombSort algorithm 
    // Print the number of items and comparisions 

    for(index = 10; index <= 10000; index = index * 10) 
    { 
     if (index == 10) 
      for(int i = 0; i < index; i++) 
       System.out.print(intArray[i] + " "); 
     comparisons = 0; 
     generate(intArray, index); 
     quickSort(intArray, 0, index - 1); 
     output(comparisons); 
    } 
} 

// Generate an array of random values between 0 and 10000 
public static void generate(int[] valueArray, int count) 
{ 
    Random generator = new Random(); 

    for(int temp = 0; temp < count; temp++) 
    { 
     valueArray[temp] = generator.nextInt(MAXINT) + 1; 
    } 
} 

// Print the number of values in the array and the number of comparisons 
public static void output(long count) 
{ 

    System.out.println("Number of values in array: " + index); 
    System.out.println("Number of comparisons required: " + count); 
    System.out.println(); 
} 

//Swap the given values and then assign them to the correct place in the array 
public static void swap(int[] value, int i, int j) 
{ 
    int temp = value[i]; 
    value[i] = value[j]; 
    value[j] = temp;   
} 

//Implement Quicksort algorithm 
public static void quickSort(int[] value, int startIndex, int endIndex) 
{ 
    int r = endIndex; 
    int l = startIndex; 
    int s; 

    if (l < r) 
    { 
     s = partition(intArray, l, r); 
     quickSort(intArray, l, s - 1); // StackOverflowError here 
     quickSort(intArray, s + 1, r); 
    } 
} 

//Partition an array into two parts 
public static int partition(int[] value, int startIndex, int endIndex) 
{  
    int r = endIndex; 
    int l = startIndex; 
    int p = value[l]; 
    int i = l; 
    int j = r + 1; 

    while(i < j) 
    { 
     while(value[i] < p) 
     { 
      i++; 
      comparisons++; 
     } 

     while(value[j] > p) 
     { 
      j--; 
      comparisons++; 
     } 

     swap(value, i, j); 
    } 

    swap(value, i, j); 
    swap(value, l, j); 

    return j; 
} 
} // end main 

Answer 1

通過重組的劃分方法，該問題已得到修復：

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

      while (true) 
      { 
        do 
        { 
         j--; 
         comparisons++; 
        } 
        while (value[j] > x); 

        do 
        { 
         i++; 
         comparisons++; 
        } 
        while (value[i] < x); 

        if (i < j) 
        { 
         swap(value, i, j); 
        } 
        else 
          return j; 
      } 
    } 

Answer 2

這裏有幾件事讓你開始調試。

您還沒有登錄你的swap，但它幾乎肯定是不正確的。您使用它的方式，其原型將爲void swap(int, int, int, int)，這意味着它不會對value陣列產生任何影響。嘗試是這樣的：

public static void swap(int[] value, int i, int j) { 
    int temp = value[i]; 
    value[i] = value[j]; 
    value[j] = temp; 
} 

，並使用它像這樣：

swap(value, i, j); 

接下來，拿到長度= 10的情況下是正確的。在排序前後打印完整的數組，確認輸出是否正確。當我在全零數組上運行你的代碼時，我得到一個無限循環。

接下來，如果您仍有問題，請添加打印語句！