LinkedList内の数字の中央値を見つける

Question

JavaでLinkedListとして保存されている数字のリストの中央値はどうやって見つかりますか？私はウィキペディアが指す選択アルゴリズムを理解していません。あなたがそれを説明できるなら、ボーナスポイント。

Answer 1

最良のアルゴリズムはQuickSelect

ある記事を読み、クイックソートを理解しよう - コンセプトは似ています。

Answer 2

プログラムをすばやくしたい場合は、リストを並べ替えて中央の要素（または2つの中間要素の平均）を選択します。

より効率的な選択アルゴリズムは、基本的に、あなたが実際にあなたのN与えられたためN番目の要素を見つけるためにソートする必要はありませんリストのビットを並べ替えないようにしてください。 （JDKは現在、箱から出して、このようなアルゴリズムを提供していません。）更新：をちょうど私の以前の記事に拡大して、より効率的な方法の例が含まれます：

• その初期parallel sortに選択を基づか各バケットのソート前に複数のバケットにデータを入れますが、中央のバケットを実際に並べ替える場所（中央値の場合）は、バケットのどちらの側でもアイテムの正確な順序が無関係
• クイックソートのような分割および征服ソートアルゴリズムをベースにしていますが、アルゴリズムが実際に必要な範囲外のサブリストをソートすることはありません。

Answer 3

中央値は、ソートされたリストの中央の数字です。 （エントリの数が不均一なリストの場合は簡単ですが、エントリ数が偶数のリストの場合は、両方の "中間の数字"の間に任意の数を入れることができます）

リストをソートし、ミドルナンバーは。

Answer 4

あなたは基本的に2つの主要なオプションがあります。

1. 簡単かつ迅速な方法 - O(nlogn)でリストをソートします。中央値は値の半分がそれよりも大きく、半分が小さい値として定義されるので、n/2番目の値を取ってください - それは中央値です。

2. パフォーマンスが非常に重要な場合は、O(n)を与えることができるさまざまな選択アルゴリズムを適用できます（ただし、最悪の場合は直線性は保証されません）。いずれの場合においても

、あなたはすべての利用可能な方法で良いラウンドアップを与える必要があります Selection Algorithms上のWikipediaのエントリを、チェックしてください。