ArrayList <BigInteger>排序算法Java

Question

我想对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进行排序？

Answer 1

你可以随时使用¹.Collections.sort(toSort)

它将简单地对ArrayList进行排序toSort.

注意 - 使用内置库通常要好得多,这些库已经过测试并针对您进行了优化,而不是重新发明轮子.大多数情况下的结果可能是:

• 更高效
• 更正确(已经处理过你可能错过的一些令人讨厌的边缘情况)
• 发展更快
• 更好地维护

PS
您的算法失败的原因是您不断删除元素toSort,然后从较大的索引读取.

举一个简短的例子,看看清单[5,2,9].
首先你有toSort = [5,2,9] , toReturn = []
什么时候i == 0,你基本上会调用:toReturn.add(toSort.remove(0));
它将导致列表:toSort = [2,9], toReturn = [5].

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

(这实际上是一个很好的例子,为什么使用内置排序通常更好!)

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