4

jdk標準ライブラリで利用可能なクイックソートまたは別のO(N.logN)ソートはありますか?

Collectionsクラスは希望をもたらさない:

実装者は、仕様自体が守られている限り、他のアルゴリズムを自由に置き換える必要があります。(たとえば、ソートで使用されるアルゴリズムはマージソートである必要はありませんが、安定している必要があります。)

そしてCollections.sort()手がかりを与えません：

sort(List<T> list) 指定されたリストをその要素の自然な順序に従って昇順に並べ替えます。

4

2 に答える 2

2

Collections.sortすべてのケースで実際に O(n log n) を保証する最適化されたマージソートであり、安定しています。リンク。

于 2013-03-11T12:31:29.007 に答える
1

ソートは に依存しArrays.sortます。ソート方法は型に依存するため、JavaDoc を読むことはそれほど明白ではありません。しきい値に応じて、変更されたマージ ソートまたは調整されたクイックソート:

 /**
 * Tuning parameter: list size at or below which insertion sort will be
 * used in preference to mergesort or quicksort.
 */
private static final int INSERTIONSORT_THRESHOLD = 7;

クイックソートとマージソートを比較した投稿は次のとおりです。クイックソートとマージソート

結論: 自分が何をしているのか本当に理解していない限り、Java 実装を信頼してください。

于 2013-03-11T12:32:06.480 に答える