java - 如何在通用类型的数组中找到三个点(未排序)的中位数？

Question

我正在尝试查找 a[p]、a[r] 和 a[q] 的中位数，其中 q = r+p/2。尽管我的程序在创建 median 方法之前就可以工作，但它还是崩溃了，所以我假设有问题。有谁知道出了什么问题吗？

这是我运行程序时显示的内容:

Welcome to DrJava.  Working directory is C:\coding
> run QuickSort
[5, 2, 7, 3, 9, 7, 10, 3, 6, 3, 7, 2, 6, 7, 2, 1]
java.lang.StackOverflowError
    at QuickSort.partition(QuickSort.java:39)
    at QuickSort.qSort(QuickSort.java:13)
    at QuickSort.qSort(QuickSort.java:13)
    at QuickSort.qSort(QuickSort.java:13)
    .
    .
    .
    at QuickSort.qSort(QuickSort.java:13)
    at QuickSort.qSort(QuickSort.java:13)
> 

最后一行不断重复。

完整代码:

import java.util.*;

public class QuickSort {
public static void main(String[] args) {
  Integer[] vals = new Integer[]{5,2,7,3,9,7,10,3,6,3,7,2,6,7,2,1};
  System.out.println(Arrays.toString(vals));
  qSort(vals,0,vals.length-1);
  System.out.println(Arrays.toString(vals));
}
public static <T extends Comparable<T>> void qSort(T[] a, int p, int r){
  if(p < r){
    int q = partition(a,p,r);
    qSort(a,p,q);
    qSort(a,q+1,r); 
  }
}
public static <T extends Comparable<T>> T median(T[] a, int p, int r){
  int q = r+p/2;
  if (a[p].compareTo(a[q]) > 0){
    if (a[q].compareTo(a[r]) > 0){
      return a[q];
    }
    else if (a[p].compareTo(a[r]) > 0){
      return a[r];
    } else{
      return a[p];
    }
  }else{
    if (a[p].compareTo(a[r]) > 0){
      return a[p];
    } else if (a[q].compareTo(a[r]) > 0){
      return a[r];
    } else{
      return a[q];
    }
  }
}
public static <T extends Comparable<T>> int partition(T[] a, int p, int r){
  T pivot = median(a,p,r);
  int i = p-1;
  int j = r+1;
  while(true){
    do{
      i++;
    }
    while(i<=r && a[i].compareTo(pivot) < 0);
    do{
      j--;
    }
    while(j>=p && a[j].compareTo(pivot) > 0);
    if(i<j){
      swap(a,i,j);
    }
    else{
      return j;
    }
  }
}
public static <T extends Comparable<T>> void swap(T[] a, int i, int j){
  T temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}
}

Answer 1

我相信你的意思是:

  int q = (r+p)/2;