我正在尝试编写一个快速排序方法作为作业的一部分，但我在 Java 中不断收到 StackOverflow 错误

Question

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

线程"main"中的异常 java.lang.StackOverflowError

at TestSorter.Tester.sort（Tester.java：6）

。（x112 重复 at TestSorter.Tester.sort（Tester.java：49））

at 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

三

点：

1. pord应该是数组的中间元素，而不是数组长度的一半。
   所以，应该是prod =a[(a.length) / 2]，
   不prod =(a.length) / 2

2. 如果数组首先只有 1 个元素，则不再需要调用该方法sort。
   也是最后一个。
   因此，添加if语句：

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

3. 当你将 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;
}