5

我将此递归 BubbleSort 算法添加到我在 lwjgl 上运行的游戏中。我正在尝试通过浮点数对“云”对象的 ArrayList 进行排序，该浮点数是该云的速度。

出于某种原因，有时我在自己调用该方法的那一行会得到一个“java.lang.StackOverflowError”。

这是代码：

public void sort() {
    for (int i = 0; i < clouds.size() - 1; i++) {
        Cloud cl1 = clouds.get(i);
        Cloud cl2 = clouds.get(i + 1);
        if (cl1.getSpeed() < cl2.getSpeed()) {
            continue;
        }
        clouds.set(i, cl2);
        clouds.set(i+1, cl1);
        this.sort();
    }
}

这是我得到的错误：

Sat May 04 20:28:45 CEST 2013 ERROR:null
java.lang.StackOverflowError
         at backgrounds.Clouds.sort(Clouds.java:224)
[...] // The line above is repeated for some hundred times.
4

5 回答 5

9

当两个连续的云具有相同的速度时，就会发生这种情况。

cl1.getSpeed() < cl2.getSpeed()

是假的，所以云被交换并sort再次被调用。在那次通话中，

cl1.getSpeed() < cl2.getSpeed()

仍然是假的，所以你再次交换并调用sort. 这将永远持续下去（或者更好：直到堆栈已满）。

更改<为<=，一切正常。

于 2013-05-04T18:52:20.173 回答
6

如果它们也相同，您的比较逻辑应该跳过两个云对象 -

改变如果 -

if (cl1.getSpeed() <= cl2.getSpeed()) {
    continue;
}
于 2013-05-04T18:53:57.550 回答
4

最好使用 java 中数组的内置排序方法Arrays.sort()来使用它，您所要做的就是覆盖 compare to 方法。这是它的外观。

@Override
public int compareTo(Book other) {
//compare logic here
}

您还必须实现 Comparable 才能做到这一点

于 2013-05-04T18:51:56.070 回答
0

可以进一步优化为

public void sort() {
    boolean swaps = false;
    for (int i = 0; i < clouds.size() - 1; i++) {
        Cloud cl1 = clouds.get(i);
        Cloud cl2 = clouds.get(i + 1);
        if (cl1.getSpeed() <= cl2.getSpeed()) {
            continue;
        }
        swaps = true;
        clouds.set(i, cl2);
        clouds.set(i+1, cl1);
    }

    //Re-Iterate all the elements only if a swap is found
    if( swaps )
      this.sort();
}
于 2013-05-04T19:01:59.590 回答
0

堆栈溢出的常见原因是错误的递归调用，这是由于递归函数没有正确的终止条件而导致的，因此它最终会永远调用自己。在您的情况下，由于严格的“<”符号，终止条件不满足，因此您必须将其更改为“<=”就是这样。

于 2013-05-06T05:51:56.033 回答