Collections.sort（...）はどのように機能しますか？

Question

私はCollections.sort（list、new MyComp（））メソッドがどのような順序でcompareメソッドを呼び出すのかを明らかにしようとしています。

Iは、従業員とのLinkedListと個人番号（K）を有する： 数である： {1,2,3,4,5,6} MyComparatorにおける比較（オブジェクトO1、オブジェクトO2）方法いくつかの番号を返します（これはこの懸念とは関係ありません）。 sort（）メソッドの比較方法はどのように比較されますか？ パラメータ1,2、2,3、3,4、4,5、そして5,6のどれかと呼んでいますか？私はそれをデバッグしますが、そこにジャンプし、1,3を比較するいくつかの奇妙なシーケンスがあります。

正確にはどうなりますか？どんなパターン？

Answer 1

具体的な比較は、内部でどのアルゴリズムを使用しているのかによって異なります。Collections.sortメソッドは要素のソートに使用しています。 Collections.sortのJavadocによると：

このクラスに含まれる多型アルゴリズムのドキュメントには、一般的に実装の簡単な説明が含まれています。そのような記述は、仕様の一部ではなく、実装上の注意とみなすべきである。実装者は、仕様自体が守られている限り、他のアルゴリズムを自由に置き換えることができます。例えば、ソートで使用されるアルゴリズムは、マージソートである必要はありませんが、安定していなければなりません。

つまり、Javaの実装では、どのソートアルゴリズムを使用しても構いませんが、同一の相対的な順序で等しい要素を保持するという条件である。これは、特定のJava実装についての知識がなければ、どのような比較が行われるかを知る方法がないことを意味します。 （私が正しく覚えていれば、JavaのOracleバージョンは実際にはCollections.sortの実装をJava 7からJava 8に切り替えたが、間違いかもしれないが）。

それは悪いことではない。コンパレータの作成の背後にあるアイデアは、ソート方法に「何をソートする必要があるかを行い、比較を行う必要がある場合は、ここでそれを行う方法です」と伝えることです。素敵な抽象です。物事をランク付けする方法を言うと、ソートのマジックブラックボックスは、それを使って物事を順番に取得します。

Answer 2

Java 7のCollections.sortのソートアルゴリズムは、挿入ソートです。