我正在尝试将 quickSort 方法编写为作业的一部分，但我在 Java 中不断收到 StackOverflow 错误

Question

这是我尝试排序的代码。在 Eclipse 的调试器模式下运行大约十分钟后，我得到了很多 Whosebug 错误。这是我的输出显示：

线程异常 "main" java.lang.WhosebugError

在 TestSorter.Tester.sort(Tester.java:6)

...（在 TestSorter.Tester.sort(Tester.java:49))

处重复 x112 次

在 TestSorter.Tester.sort(Tester.java:49)

public static int[] sort(int[] a) {
                           int prod = (a.length)/2, b = lessThan(a, prod), c = greaterThan(a, prod), d = equalTo(a, prod);
    int[] first, last, mid;
    first = new int[b];
    last = new int[c];
    mid = new int[d];
    int[] fina = new int[a.length];
    int f = 0, l = 0, m = 0;

    if (isSorted(a))
        return a;

    for (int x = 0; x < a.length; x++) {
        if (a[x] < prod) {
            first[f] = a[x];
            f++;
        }
        else if (a[x] > prod) {
            last[l] = a[x];
            l++;
        }
        else if (a[x] == prod) {
            mid[m] = a[x];
            m++;
        }
    }
    if (m == a.length)
        return a;

                           first = sort(first);

    last = sort(last);

    for (int x = 0; x < b; x++) {
        fina[x] += first[x];
    }
    for (int x = 0; x < d; x++) {
        fina[x + b] = mid[x];
    }
    for (int x = 0; x < c; x++) {
        fina[x + b + c] = last[x];
    }

    return fina;
}

我的支持方式如下：

private static int lessThan(int[] a, int prod) {
    int less = 0;
    for (int x = 0; x < a.length; x++) {
        if (a[x] < prod) {
            less++;
        }
    }
    return less;
}

private static int greaterThan(int[] a, int prod) {
    int greater = 0;
    for (int x = 0; x < a.length; x++) {
        if (a[x] > prod) {
            greater++;
        }
    }
    return greater;
}

private static int equalTo(int[] a, int prod) {
    int equal = 0;
    for (int x = 0; x < a.length; x++) {
        if (a[x] == prod) {
            equal++;
        }
    }
    return equal;
}

private static boolean isSorted(int[] a) {
    for (int x = 0; x < a.length - 1; x++) {
        if (a[x] > a[x + 1])
            return false;
    }
    return true;
}

Answer 1

想必问题是你的"prod"不在你的数组域内。因此 "first" 或 "last" 与输入数组的大小相同，并且您有无限递归。尝试将 prod 设置为您要排序的数组中的一个元素。

Answer 2

三分：

pord 应该是数组的中间元素，而不是数组长度的一半。
所以，应该是 prod =a[(a.length) / 2],
不是 prod =(a.length) / 2
如果数组第一个只有1个元素，则不需要再调用方法sort。
还有 last.
因此，添加 if 语句：
```
if (1 < first.length) {
    first = sort(first);
}
```
将last的元素追加到fina时，索引应该是x+b+d，即first个元素(b) + mid 个元素（d）。不是 x+b+c.
因此，将 fina[x + b + c] = last[x]; 更改为 fina[x + b + d] = last[x];

嗯，方法sort可能是这样的：

public static int[] sort(int[] a) {
    int prod =a[(a.length) / 2], b = lessThan(a, prod), c = greaterThan(a,
            prod), d = equalTo(a, prod);
    int[] first, last, mid;
    first = new int[b];
    last = new int[c];
    mid = new int[d];
    int[] fina = new int[a.length];
    int f = 0, l = 0, m = 0;

    if (isSorted(a) )
        return a;

    for (int x = 0; x < a.length; x++) {
        if (a[x] < prod) {
            first[f] = a[x];
            f++;
        } else if (a[x] > prod) {
            last[l] = a[x];
            l++;
        } else if (a[x] == prod) {
            mid[m] = a[x];
            m++;
        }
    }
    if (m == a.length)
        return a;

    if (1 < first.length) {
        first = sort(first);
    }

    if (1 < last.length) {
    last = sort(last);
    }

    for (int x = 0; x < b; x++) {
        fina[x] += first[x];
    }
    for (int x = 0; x < d; x++) {
        fina[x + b] = mid[x];
    }

    for (int x = 0; x < c; x++) {
        fina[x + b + d] = last[x];
    }

    return fina;
}

我正在尝试将 quickSort 方法编写为作业的一部分，但我在 Java 中不断收到 StackOverflow 错误

I am trying to write a quickSort method as part of an assignment, but I keep getting a StackOverflow error in Java

java

stack-overflow

sorting