Quicksort（Java）导致stack.verFlow在array.length> 60k
我的代码正常工作（据我所知），直到我的输入数组大小（ a.length ）大约为62,000，此时我一直得到StackOverFlowError 。 我以前曾使用2次递归调用quicksort （小于和大于数据透视q ），然后我切换到尾递归。 如您所见，我选择了pivot作为数组末尾的值。 我知道这不是选择枢轴的最佳方法，但我仍然不应该看到StackOverFlowError的数组大小这么小，对吗？ 可能是什么导致了这个？ 提前致谢！ 这是我的代码：
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等人）。 通过随机化排序（选择随机枢轴）， 没有特定的输入引发其最坏情况的行为 。
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(); } }
给定正确的输入，您的实现将为数组的每个元素递归一次。 在默认配置中，60,000个递归调用很容易在Java中溢出堆栈。