3

我想对 ArrayList 进行排序，使其从最小到最大。我有以下代码：

public static ArrayList<BigInteger> sortBigInteger(ArrayList<BigInteger> toSort){
    ArrayList<BigInteger> toReturn = new ArrayList<BigInteger>();
    toReturn.add(toSort.remove(0));
    for (int i = 0; i < toSort.size(); i++){
        BigInteger n = toSort.get(i);
        boolean eval = false;
        in: for (int a = 0; a < toReturn.size(); a++){
            if (n.compareTo(toReturn.get(a)) < 0){
                toReturn.add(a, toSort.remove(i));
                eval = true;
                break in;
            }
        }
        if (!eval) toReturn.add(toSort.remove(i));
    }
    toSort = toReturn;
    return toReturn;
}

但是，我失去了元素。使用大小为 32 的 ArrayList，我得到大小为 15 的 ArrayList。额外的删除发生在哪里？
主要问题：如何对 ArrayList 进行排序？

4

1 回答 1

10

您始终可以使用1。Collections.sort(toSort)

它只会对 ArrayList 进行排序toSort。

注意 - 使用已经为您构建测试和优化的内置库通常要好得多，而不是重新发明轮子。在大多数情况下，结果可能是：

  • 更高效
  • 更正确（已经处理了一些你可能错过的讨厌的边缘情况）
  • 开发速度更快
  • 更好的维护

PS
您的算法失败的原因是您不断从中删除元素toSort，然后从更大的索引中读取。

举个简短​​的例子，看看 list [5,2,9]。
首先你有toSort = [5,2,9] , toReturn = []
When i == 0，你基本上会调用：toReturn.add(toSort.remove(0));
它将导致列表：toSort = [2,9], toReturn = [5]。

但是，在下一次迭代 -i==1中，您将检查索引为 1 的元素，现在是 9，而不是 2！你错过了一个元素！

（这实际上是一个很好的例子，为什么使用内置排序通常更好！）

（1）假设您只想对您的评论进行排序，而不是将其作为自我改进或任务。如果您对排序算法感兴趣，您可能会发现排序算法的维基百科页面很有帮助，尤其是在 java 中实际使用的那个 - TimSort。

于 2012-12-12T23:14:10.007 回答