Java 快速排序 - 堆栈内存溢出

Question

我正在尝试实现一个使用如下计算的主元的快速排序版本：

pivot = ( a[start] + a[end] + a[size/2] ) / 3

ATM 它在大小为 6 或更小的数组上完美运行，但是一旦对大小为 7 或更大的数组进行排序，程序就会进入无限循环。到目前为止，我对递归的理解还不牢固，所以我怀疑它在那里崩溃了。我知道它在检查索引 4 和 6 时进入循环，然后只检查那些索引

编辑：添加了对 quickSort() 的调用，并修复了一些格式

public static void quickSort(double[] list, int start, int end){
    if (end - start > 1){
      int pivot = split(list, start, end);
      quickSort(list, start, pivot - 1);
      quickSort(list, pivot + 1, end);
    } 
    if ( (end - start) == 1){
      if (list[start] > list[end]){
        double temp = list[start];
        list[start] = list[end];
        list[end] = temp;
      }
    }
  }

  public static int split(double[] list, int start, int end){
    // splitPoint = (a[begin] + a[end] + a[size/2]) / 3
    int size = end - start + 1;
    double pivotValue = (list[start] + list[end] + list[size/2]) / 3;

    int leftPosition = start;
    int rightPosition = end;
    double temp = 0;

    while (true){
      // find a value to swap on the left side of pivot
      while ( (leftPosition <= rightPosition) && (list[leftPosition] <= pivotValue) ){
        leftPosition++;
      }

      // find a value to swap on the right side of pivot
      while ( (rightPosition >= leftPosition) && (list[rightPosition] >= pivotValue) ){
        rightPosition--;
      }
      // if positions pass each other
      if (rightPosition < leftPosition){
        break;
      } else {
        // swap values
        temp = list[leftPosition];
        list[leftPosition] = list[rightPosition];
        list[rightPosition] = temp;
      }
    }
    return rightPosition;
  }

  public static void main(String[] args){
      double[] list = {7, 6, 5, 4, 3, 2, 1};
      quickSort(list, 0, list.length-1);
  }

Answer 1

算法的第一步是：

Pick an element, called a pivot, from the array.

这个表达式不会那样做：

(list[start] + list[end] + list[size / 2]) / 3

它只计算 3 个数字的平均值，其中一个可以在正在排序的分区之外（参见开始 +）。
所以给定这个数组：{1,2,3,4,5,6,7}、start = 4 和 end = 6 所选择的项目将是 (5 + 7 + 2)/3 = 4.(6)7 而这个不是的元素分区 {5,6,7}.
你应该做的是在 start...end 范围内选择一个数字作为枢轴的索引。

开始+

我相信您实际考虑的主元（分区的第一个、最后一个和中间元素的平均值）是：

(list[start] + list[end] + list[start + (size / 2)]) / 3.0

尽管此表达式不会从分区中选取一个元素，但它会选取一个不等于分区中所有值 bigger/smaller 的值，并且它会起作用。

具有 /3 枢轴的工作解决方案：

void quickSort(double[] list, int start, int end) {
    int size = end - start + 1;
    // this is the 'classic' pivot
    // double pivotValue = list[start + (end - start) / 2];
    double pivotValue = (list[start] + list[end] + list[start + (size / 2)]) / 3.0;
    int leftPosition = start;
    int rightPosition = end;

    while (leftPosition <= rightPosition) {
        while (list[leftPosition] < pivotValue) {
            leftPosition++;
        }
        while (list[rightPosition] > pivotValue) {
            rightPosition--;
        }

        if (leftPosition <= rightPosition) {
            exchange(list, leftPosition, rightPosition);
            leftPosition++;
            rightPosition--;
        }
    }
    if (start < rightPosition)
        quickSort(list, start, rightPosition);
    if (leftPosition < end)
        quickSort(list, leftPosition, end);
}

void exchange(double[] list, int i, int j) {
    double temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

Java 快速排序 - 堆栈内存溢出

Java Quicksort - Stack Overflow

java

stack-overflow

quicksort

infinite-loop

开始+

具有 /3 枢轴的工作解决方案：