使用Quicksort Java实现的Stackoverflow

在java中实现quicksort时遇到一些问题。 我运行这个程序时出现stackoverflow错误，我不确定为什么。 如果有人能够指出错误，那就太好了。

si是起始指数。 ei是结束指数。

public static void qsort(int[] a, int si, int ei){ //base case if(ei=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 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

首先，您应该按照Keith的建议修复qsort递归调用的边界，否则您总是一遍又一遍地对整个数组进行排序。 你必须调整你的分区循环：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

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

Answer 3

您可能手上有无限的递归错误。 从我的快速扫描不确定，但……

即使你不这样做，你仍然会在这个实现中使用大量的堆栈。 足以导致堆栈溢出。 如果用100万个已经排序的项目调用它会发生什么？ 你将它们分成1和999,999项，然后递归。 因此，您需要100万个堆栈帧才能完成这项工作。

有很多方法可以解决这个问题，包括递归两个范围中较小的一个并迭代两个中较大的一个，或者在堆数据结构中自己实现堆栈等等。你可能想要做得更好，尽管，因为深层堆栈也意味着你正在吹过O（n lg n）排序界限。

ps这里的错误是：

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

应该

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

Answer 4

你可以试试这个：

 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; } 

来源： 代码2学习：快速排序算法教程

Answer 5

 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 6

//刚刚为此实现了测试人员类，它将起作用

public int [] sort（int [] A，int from，int to）{

 if(from1) sort(A,from, pivot-1); if(pivot+1 

}

public int partition（int A []，int from，int to）{

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

Answer 7

这应该是相当明确的。 下面的代码使用此图像更有意义。

 public void quickSort(long[] a){ int startingIndex = 0; int endingIndex = a.length - 1; qsort(a, startingIndex, endingIndex); } private void qsort(long[] a, int startingIndex, int endingIndex){ if (startingIndex < endingIndex){ int middleIndex = partition(a, startingIndex, endingIndex); qsort(a, startingIndex, middleIndex-1); qsort(a, middleIndex+1, endingIndex); } } private int partition(long[] a, int startingIndex, int endingIndex){ long pivot = a[endingIndex]; int endWall = endingIndex; int wall = 0; while (wall < endWall){ if (a[wall] < pivot){ wall++; } else { a[endWall] = a[wall]; a[wall] = a[endWall - 1]; a[endWall - 1] = pivot; endWall--; } } return wall; } 

请享用！

Answer 8

 public class MyQuickSort { private int array[]; private int length; public void sort(int[] inputArr) { if (inputArr == null || inputArr.length == 0) { return; } this.array = inputArr; length = inputArr.length; quickSort(0, length - 1); } private void quickSort(int lowerIndex, int higherIndex) { int i = lowerIndex; int j = higherIndex; // calculate pivot number, I am taking pivot as middle index number int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; // Divide into two arrays while (i <= j) { /** * In each iteration, we will identify a number from left side which * is greater then the pivot value, and also we will identify a number * from right side which is less then the pivot value. Once the search * is done, then we exchange both numbers. */ while (array[i] < pivot) { i++; } while (array[j] > pivot) { j--; } if (i <= j) { exchangeNumbers(i, j); //move index to next position on both sides i++; j--; } } // call quickSort() method recursively if (lowerIndex < j) quickSort(lowerIndex, j); if (i < higherIndex) quickSort(i, higherIndex); } private void exchangeNumbers(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String a[]){ MyQuickSort sorter = new MyQuickSort(); int[] input = {24,2,45,20,56,75,2,56,99,53,12}; sorter.sort(input); for(int i:input){ System.out.print(i); System.out.print(" "); } } } 

Answer 9

Quicksort对输入恰好是正确的顺序敏感，在这种情况下，它可以跳过一些交换。 Mergesort没有任何这样的优化，与Mergesort相比，这也使得Quicksort更快一些。

为什么快速排序比合并排序更好