使用Quicksort Java實現的Stackoverflow

Question

在java中實現快速排序時遇到了一些問題。我運行這個程序時遇到了一個stackoverflow錯誤，我不確定爲什麼。如果有人能指出這個錯誤，那會很好。

si是起始索引。 ei是結束索引。

public static void qsort(int[] a, int si, int ei){ 

    //base case 
    if(ei<=si || si>=ei){} 


    else{ 
     int pivot = a[si]; 
     int length = ei - si + 1; 
     int i = si+1; int tmp; 

     //partition array 
     for(int j = si+1; j<length; j++){ 
      if(pivot > a[j]){ 
       tmp = a[j]; 
       a[j] = a[i]; 
       a[i] = tmp; 

       i++; 
      } 
     } 

     //put pivot in right position 
     a[si] = a[i-1]; 
     a[i-1] = pivot; 

     //call qsort on right and left sides of pivot 
     qsort(a, 0, i-2); 
     qsort(a, i, a.length-1); 
    } 
} 

Answer 1

首先，你應該解決的qsort遞歸調用的邊界由Keith的建議，否則你總是全陣列式遍地整理再次。你必須調整你的分區循環：j是一個索引，從子數組的開始到結束（包括最後一個元素）。所以你必須從si + 1循環到ei（包括ei）。

所以這是更正的代碼。我運行了一些測試用例，似乎很好。

public static void qsort(int[] a, int si, int ei){ 
    //base case 
    if(ei<=si || si>=ei){} 

    else{ 
     int pivot = a[si]; 
     int i = si+1; int tmp; 

     //partition array 
     for(int j = si+1; j<= ei; j++){ 
      if(pivot > a[j]){ 
       tmp = a[j]; 
       a[j] = a[i]; 
       a[i] = tmp; 

       i++; 
      } 
     } 

     //put pivot in right position 
     a[si] = a[i-1]; 
     a[i-1] = pivot; 

     //call qsort on right and left sides of pivot 
     qsort(a, si, i-2); 
     qsort(a, i, ei); 
    } 
} 

Answer 2

您可能手上有無限的遞歸錯誤。不知道從我的快速掃描，但...

即使你不這樣做，你仍然會使用批次堆棧與此實現。足以導致堆棧溢出。如果你用100萬個已經分類的物品進行調用會發生什麼？你將它們分成1和999,999項，然後遞歸。所以你需要100萬個棧幀來完成這個工作。

有很多方法可以解決這個問題，包括遞歸兩個範圍中較小的一個，迭代兩個範圍中較大的一個，或者自己在堆數據結構中實現堆棧等等。您可能想要做得更好儘管如此，由於深度堆棧也意味着你正在通過O（n lg n）排序界限。

p.s.錯誤是在這裏：

qsort(a, 0, i-2); 
qsort(a, i, a.length-1); 

應該

qsort(a, si, i-2); 
qsort(a, i, ei); 

Answer 3

你可以試試這個：

public void sort(int[] A) { 
     if (A == null || A.length == 0) 
      return; 
     quicksort(A, 0, A.length - 1); 
    } 

    public void quicksort(int[] A, int left, int right) { 
     int pivot = A[left + (right - left)/2]; 
     int i = left; 
     int j = right; 
     while (i <= j) { 
      while (A[i] < pivot) { 
       i++; 
      } 
      while (A[j] > pivot) { 
       j--; 
      } 
      if (i <= j) { 
       exchange(i, j); 
       i++; 
       j--; 
      } 
     } 

     if(left < j) 
      quicksort(A,left,j); 
     if(i < right) 
      quicksort(A,i,right); 
    } 

    public void exchange(int i, int j){ 
     int temp=A[i]; 
     A[i]=A[j]; 
     A[j]=temp; 
    } 

    public String toString() { 
     String s = ""; 
     s += "[" + A[0]; 
     for (int i = 1; i < A.length; i++) { 
      s += ", " + A[i]; 
     } 
     s += "]"; 
     return s; 
    } 

來源：Code 2 Learn: Quick Sort Algorithm Tutorial

Answer 4

import java.util.Arrays; 


public class QuickSort { 


    public static int pivot(int[] a, int lo, int hi){ 
     int mid = (lo+hi)/2; 
     int pivot = a[lo] + a[hi] + a[mid] - Math.min(Math.min(a[lo], a[hi]), a[mid]) - Math.max(Math.max(a[lo], a[hi]), a[mid]); 

     if(pivot == a[lo]) 
      return lo; 
     else if(pivot == a[hi]) 
      return hi; 
     return mid; 
    } 

    public static int partition(int[] a, int lo, int hi){ 

     int k = pivot(a, lo, hi); 
     //System.out.println(k); 
     swap(a, lo, k); 
     //System.out.println(a); 
     int j = hi + 1; 
     int i = lo; 
     while(true){ 

      while(a[lo] < a[--j]) 
       if(j==lo) break; 

      while(a[++i] < a[lo]) 
       if(i==hi) break; 

      if(i >= j) break; 
      swap(a, i, j); 
     } 
     swap(a, lo, j); 
     return j; 
    } 

    public static void sort(int[] a, int lo, int hi){ 
     if(hi<=lo) return; 
     int p = partition(a, lo, hi); 
     sort(a, lo, p-1); 
     sort(a, p+1, hi); 
    } 

    public static void swap(int[] a, int b, int c){ 
     int swap = a[b]; 
     a[b] = a[c]; 
     a[c] = swap; 
    } 

    public static void sort(int[] a){ 
     sort(a, 0, a.length - 1); 
     System.out.print(Arrays.toString(a)); 
    } 

    public static void main(String[] args) { 
     int[] arr = {5,8,6,4,2,9,7,5,9,4,7,6,2,8,7,5,6}; 
     sort(arr); 
    } 
} 

試試這個。它肯定會起作用。

Answer 5

//剛實施的測試類，這和它會工作

（來自INT到INT [] A，INT）{

if(from<to){ 
    int pivot=partition(A,from,to); 
    if(pivot>1) 
     sort(A,from, pivot-1); 

    if(pivot+1<to) 
     sort(A, pivot+1, to); 


} 

return array; 

}

公衆詮釋[]排序

公衆詮釋分區（INT A []，INT從，INT到）{

while(from < to){ 
    int pivot=A[from]; 

    while(A[from]<pivot) 
     from++; 

    while(A[to]>pivot) 
     to--; 


    if(from<to) 
     swap(A,to,from); 



} 
    return to; 
} 

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

Answer 6

快速排序是輕微敏感輸入恰好按照正確的順序，在這種情況下，它可以跳過一些掉期。 Mergesort沒有任何這樣的優化，與Mergesort相比，這也使得Quicksort更快一些。

Why Quick sort is better than Merge sort

Answer 7

int partition(int array[], int too_big_index, int too_small_index) 
{ 
    int x = array[too_big_index]; 
    int i = too_big_index; 
    int j = too_small_index; 
    int temp; 
    do 
    {     
     while (x <array[j]) 
     { 
       j --; 
     } 
     while (x >array[i]) 
     { 
       i++; 
     } 
      if (i < j) 
     { 
       temp = array[i];  
       array[i] = array[j]; 
       array[j] = temp; 
     } 
    }while (i < j);  
    return j;   // middle 
} 

void QuickSort(int num[], int too_big_index, int too_small_index) 
{ 
     // too_big_index = beginning of array 
     // too_small_index = end of array 

    int middle; 
    if (too_big_index < too_small_index) 
    { 
      middle = partition(num, too_big_index, too_small_index); 
      QuickSort(num, too_big_index, middle); // sort first section 
      QuickSort(num, middle+1, too_small_index); // sort second section 
    } 
    return; 
} 



void main() 
{ 
    int arr[]={8,7,13,2,5,19,1,40,12,34}; 

    QuickSort(arr,0,9); 
    for(int i=0;i<10;i++) 
     System.out.println(arr[i]); 
}