快速排序和中值实现的堆栈溢出错误

Question

首先，我只想声明这是一道我已经进行了大量尝试的家庭作业题。

有人要求我修改 Java 中的快速排序，使用公式 i * (n-1) /8

将主元设置为数组中 9 个值的伪中值

我写了一个 computeMedian 方法，它接受 3 个整数，确定最高的，然后 returns 那个值。

代码：

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 方法中使用它，该方法采用当前 array, 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 {}部分。我会注意到 return computeMedian(a[from], a[(to)/2] , a[to]); 如果我把它放在那里，它在 > 40 部分起作用，但这只是 3 个值的中值，而不是 3 组中值的中值。

目前这是我 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]),...etc我遇到了同样的堆栈溢出问题，但它往往会移动到我代码的不同部分并让我陷入困境。

如果有人需要，我可以 post 更多片段，但我认为我的问题可能就在这里。

感谢您的帮助。我仍在学习，我认为掌握这一点完全可以帮助我在未来自行解决问题。

以下是堆栈跟踪中的问题行：第 16 行：int p = modPartition(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);
    }

Answer 1

现在您实际上已经包含了堆栈溢出问题的代码和错误消息，我们可以帮助您。

从您的堆栈跟踪中，我们可以看到无限递归可能第二次调用 modSort，因为第 18 行重复了。

由于该调用和传入参数之间的唯一区别是第二个参数，我敢打赌 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);
}

生成的输出应该非常清楚地表明出了什么问题。

Answer 2

转载更正

已添加代码以重现错误...

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));
}

正在调试。为 WhosebugError 设置断点（如评论中所建议）无效。所以我在行（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);
    }
}

那么它对我的例子来说工作得很好。我在这一点上停止它（必须睡一会儿）。

我认为您应该尝试熟悉调试器。我想你应该更容易理解。

快速排序和中值实现的堆栈溢出错误

Stack overflow error with Quicksort and median implementation

java

sorting

quicksort

median-of-medians