滞留在随机转动

Question

一个简单的快速排序实现我检讨算法的东西，停留在简单的快速排序算法的实现在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) { 
       i++; 
      } 
      while (arr[j] > pivot) { 
       j--; 
      } 
      if (i < j) { 
       int t = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = t; 
       i++; 
       j--; 
      } 
     } 
     if (i - start > 1) { 
      _sort(start, i); 
     } 
     if (end - i > 1) { 
      _sort(i, end); 
     } 
    } 
} 

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

的情况是：当它到达一个子阵列，因为这{3,5,5}，我==启动== 0和j ==端== 2。最后5和5交换，我变成2，j变成1（i ++和j--）。然后，因为i - start>1它会一遍又一遍地调用_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--; 
     }