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、より大きなインデックスから読み取るためです。

簡単な例については、リストをご覧ください[5,2,9]。
最初にtoSort = [5,2,9] , toReturn = []
Wheni == 0があり、基本的には invoke:toReturn.add(toSort.remove(0));
になります。リスト: になりますtoSort = [2,9], toReturn = [5]。

しかし、次の反復では - i==1、インデックス 1 の要素をチェックします。これは現在 2 ではなく 9 です! あなたは要素を逃しました！

(これは実際、組み込みの並べ替えを使用する方が通常は優れている理由の良い例です!)

(1) あなたのコメントから、あなたはそれを整理したいだけで、自己改善やタスクとしてそれをしていないと仮定します. 並べ替えアルゴリズムに興味がある場合は、並べ替えアルゴリズムに関するウィキペディアのページ、特に Java で実際に使用されているもの - TimSortが役立つことがあります。

于 2012-12-12T23:14:10.007 に答える