使用随机数据块进行简单的快速排序实现

我正在审查算法的东西，并坚持在Java中的简单的快速排序算法实现

import java.util.Arrays; import java.util.Random; public class QuickSort { int arr[]; boolean randomPick; Random rand = null; public QuickSort(int[] inputArray) { arr = inputArray; randomPick = false; } public QuickSort(int[] inputArray, boolean random) { arr = inputArray; if (random) { randomPick = true; rand = new Random(System.currentTimeMillis()); } else { randomPick = false; } } public int[] sort() { int start = 0; int end = arr.length - 1; try { _sort(start, end); } catch (StackOverflowError e) { System.out.println("StackOverflow: " + Arrays.toString(arr)); } return arr; } private void _sort(int start, int end) { int i = start; int j = end; int pivotLoc; if (!randomPick) { pivotLoc = (j + i) / 2; } else { pivotLoc = rand.nextInt(j - i) + i; } int pivot = arr[pivotLoc]; while (i < j) { // swapping numbers around the pivot while (arr[i]  pivot) { j--; } if (i  1) { _sort(start, i); } if (end - i > 1) { _sort(i, end); } } } 

代码可以选择中间数作为枢轴，也可以随机选择一个数字作为数据透视表，并通过循环调用_sort对数组进行排序。 它适用于第一种情况但在第二种情况下失败。

情况是：当它到达一个子arrays时，这个{3,5,5}，i == start == 0和j == end == 2。 最后交换5和5，i变为2，j变为1（i ++和j–）。 然后，因为i - start>1它将_sort调用_sort并最终引起stackoverflow错误。 但是错误应该发生在第一种情况下（固定枢轴），到目前为止还没有发生……

我不知道我的代码有什么问题。 我知道阅读其他人编写的代码并不是很乐意吗？

Answer 1

您在递归条件中犯了一个小错误， start和end比较都是针对i ， start应该是针对j

你有：

  if (i - start > 1) { _sort(start, i); } if (end - i > 1) { _sort(i, end); } 

需要是：

  if (j > start) { _sort(start, j); } if (end > i) { _sort(i, end); } 

你的i和j比较需要允许等于：

  // here ----v if (i <= j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; i++; j--; }