使用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]); 
}