我的代码正常工作（据我所知），直到我的输入数组大小（ a.length ）大约为62,000，此时我一直得到的StackOverflowError 。我以前曾使用2次递归调用 quicksort （小于和大于数据透视 q ）然后我切换尾递归。如您所见，我选择了pivot作为数组末尾的值。我知道这不是选择数据透视表的最佳方法，但我仍然不应该看到 StackOverFlowError s，数组大小这么小，对吧？可能是什么导致了这个？提前致谢！这是我的代码：
My code works properly (to my knowledge) up until my input array size (a.length) is around 62,000 at which time I consistently get a StackOverFlowError. I previously had used 2 recursive calls to quicksort (less than, and greater than the pivot q) and then I switched to tail recursion. As you can see, I'm selecting the pivot to be the value at the end of the array. I know this isn't the best way to choose a pivot, but I still shouldn't be seeing StackOverFlowErrors with an array size this small, right? What could be causing this? Thanks in advance! Here's my code:
public static void quicksort(int[] a, int p, int r) { int q; while (p < r) { q = partition(a, p, r); quicksort(a, p, q - 1); p = q + 1; } } public static int partition(int[] a, int p, int r) { int j = p - 1; int x = a[r]; for (int i = p; i < r; i++) { if (a[i] <= x) { j++; swap(a, i, j); } } j++; swap(a, j, r); return j; } private static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }推荐答案
最坏情况输入（排序顺序）使快速排序Θ（n ^ 2）。 分区总是在分区的一侧放置一个元素（Cormen等人）。通过随机化排序（选择随机数据）没有特定的输入引发其最坏情况行为。
The worst-case input (sorted order) makes quicksort Θ(n^2). Partition always puts a single element on one side of the partition (Cormen et al.). By randomizing the sort (choosing a random pivot) no particular input elicits its worst-case behavior.
import java.util.Random; public class Quicksort { private static Random rand = new Random(); public static void quicksort(int[] arr, int left, int right) { if (left < right) { int pivot = randomizedPartition(arr, left, right); quicksort(arr, left, pivot); quicksort(arr, pivot + 1, right); } } private static int randomizedPartition(int[] arr, int left, int right) { int swapIndex = left + rand.nextInt(right - left) + 1; swap(arr, left, swapIndex); return partition(arr, left, right); } private static int partition(int[] arr, int left, int right) { int pivot = arr[left]; int i = left - 1; int j = right + 1; while (true) { do j--; while (arr[j] > pivot); do i++; while (arr[i] < pivot); if (i < j) swap(arr, i, j); else return j; } } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // Sort 100k elements that are in reversed sorted order public static void main(String[] args) { int arr[] = new int[100000]; for (int i = 0; i < arr.length; i++) arr[i] = arr.length - i; System.out.println("First 20 elements"); System.out.print("Before sort: "); for (int i = 0; i < 20; i++) System.out.print(arr[i] + " "); System.out.println(); quicksort(arr, 0, arr.length - 1); System.out.print("After sort: "); for (int i = 0; i < 20; i++) System.out.print(arr[i] + " "); System.out.println(); } }