首先，我要声明这是一个家庭作业问题，我已经做了大量的尝试。
我被要求在Java修改快速排序，使用公式i*（n-1） /8将透视设置为数组中9个值的psuedo中位数
我编写了一个computeMedian方法，它接受3个整数，确定最高值，然后返回该值。
代码：
public static int computeMedian(int x, int y, int z)
{
if((x >= y && x <= z) || (x >= z && x <= y)) {return x;}
else if((y >= x && y <= z) || (y >= z && y <= x)) {return y;}
else if((z >= x && z <= y) || (z >= y && z <= x)) {return z;}
else { return 0; }
}
然后我在我的findPivot方法中使用它，该方法获取当前的数组、from、to值并使用它们来构造一个透视
这是该代码：
public static int findPivot(int[] a, int from, int to)
{
if(a.length <= 7)
{
return a[(to)/2];
}
else if(a.length > 7 && a.length <= 40)
{
return computeMedian(a[from], a[(to)/2] , a[to]);
}
else
{
int x = computeMedian(a[0 * (to) / 8], a[1 * (to) / 8], a[2 * (to) / 8]);
int y = computeMedian(a[3 * (to) / 8], a[4 * (to) / 8], a[5 * (to) / 8]);
int z = computeMedian(a[6 * (to) / 8], a[7 * (to) / 8], a[8 * (to) / 8]);
return computeMedian(x,y,z);
}
}
这个方法可以很好地对任何小于或等于40的数组进行排序，但是一旦它大于40，我就会收到一个堆栈溢出错误，导致我在else{}部分中的computeMedian方法。我会注意到返回computeMedian（a[from]，a[（to）/2]，a[to]）；在
目前，这就是我将findPivot插入快速排序分区方法的方式：
private static int modPartition(int[] a, int from, int to)
{
int pivot = findPivot(a, from, to);
int i = from - 1;
int j = to + 1;
while(i < j)
{
i++; while (a[i] < pivot) { i++; }
j--; while (a[j] > pivot) { j--; }
if (i < j) { swap(a, i, j); }
}
return j;
}
我非常困惑为什么我的computeMedian方法无法在更大的数据集上工作。我尝试过通过for循环将i*（n-1）/8值放入数组中，对它们进行排序并返回中间的值，以及将值放入数组p并调用computeMedian（computeMedian（p[0]， p[1]，p[2]），computeMedian（p[3]，p[4]，p[5]），……等等，我遇到了相同的堆栈溢出问题，但它往往会移动到我代码的不同部分并引导我绕圈。
如果有人需要，我可以发布更多的片段，但我认为我的问题可能就在这里。
谢谢你的帮助。我还在学习，我认为掌握这一点将完全帮助我在未来独自解决问题。
以下是堆栈跟踪中的问题行：第16行：int p=modDeftion（a， from，to）；第18行modSort（a，p 1，to）；第23行int pivot=findPivot（a，from，to）；
这也是我的整个modSort方法：
public static void modSort(int[]a, int from, int to)
{
if(from >= to) { return; }
int p = modPartition(a, from, to);
modSort(a, from, p);
modSort(a, p+1, to);
}
转载并更正
添加代码以重现错误…
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public static void main(String[] args) {
// Generate a sample
// ArrayList<Integer> list = new ArrayList<>(64);
// for (int i = 0; i < 64; i++) list.add(i);
// Collections.shuffle(list);
// System.out.println(list);
int[] arr = {40, 9, 2, 62, 8, 42, 46, 23, 61, 45, 63, 48, 43, 36, 33, 32, 1, 55, 7, 17, 16, 25, 5, 26, 22, 11, 56, 38, 60, 31, 58, 29, 51, 34, 24, 54, 4, 3, 30, 20, 57, 18, 50, 44, 41, 12, 59, 6, 53, 39, 37, 35, 28, 13, 14, 15, 0, 19, 49, 52, 21, 27, 47, 10};
modSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
调试。为StackOverFlowError设置断点（如注释中建议的）不起作用。所以我在行（modSort的开头）使用常规断点。
对于这个示例，数据开始在modSort上进行无限递归，其中from=3； to=5。对于该范围，支点p=2，这似乎不正常。
我责怪findPivot（a， from，to）方法。看起来很适合为整个a找到枢轴，但不适合范围。尝试此更正：
public static int findPivot(int[] a, int from, int to) {
final int rangeLength = to - from + 1;
if(rangeLength <= 7) {
return a[(from + to)/2];
} else if(rangeLength <= 40) { // why test "a.length > 7" ?
return computeMedian(a[from], a[(from + to)/2] , a[to]);
} else {
final int rangeLength_8 = (to - from) / 8;
int x = computeMedian(a[from], a[from + rangeLength_8], a[from + 2 * rangeLength_8]);
int y = computeMedian(a[from + 3 * rangeLength_8], a[from + 4 * rangeLength_8], a[from + 5 * rangeLength_8]);
int z = computeMedian(a[from + 6 * rangeLength_8], a[from + 7 * rangeLength_8], a[to]);
return computeMedian(x,y,z);
}
}
然后它对我的例子来说工作得很好。我在这一点上停止了它（必须睡一会儿）。
我认为你应该试着熟悉调试器。我认为你应该更容易弄清楚。
现在您已经实际包含了堆栈溢出问题的代码和错误消息，我们可以为您提供帮助。
从您的堆栈跟踪中，我们可以看到无限递归很可能是对modSort的第二次调用，因为重复了第18行。
由于该调用和传入参数之间的唯一区别是第2个参数，因此我打赌p小于from。
确认这一点的最佳方法是插入一个好的老式print语句。
public static void modSort(int[]a, int from, int to)
{
if(from >= to) { return; }
int p = modPartition(a, from, to);
System.out.println("from=" + from + ", to=" + to + ", p=" + p);
modSort(a, from, p);
modSort(a, p+1, to);
}
结果输出应该显示出非常清晰的错误模式。
