選択アルゴリズム
整列されていないデータのリストがあるとき、最小値を求めるには全要素を調べる必要があるため(さもなくば最小値を見逃す可能性がある)、線形時間 (Ω(n)) を必要とする。リストを作成する際に全データが常に整列するようにすれば、k 番目に大きい値の選択も簡単になる。しかし、そのためにはリストの途中へのデータの挿入に線形時間を必要とする(2つのリストのマージと同様である)。
準線形時間で順序統計量を求める戦略は、データを選択を行うのに適したデータ構造に格納するものである。そのようなデータ構造として木構造ベースのものと度数分布表がある。
最小値(または最大値)だけが必要な場合、優先度付きキューが適している。これは最小値(または最大値)を一定時間で探すことができ、他の挿入などの操作も O(log n) かそれよりよい性能を示す。より一般的には平衡2分探索木を使えば、要素の挿入も k 番目に大きい値の選択も O(log n) の時間で可能である。各ノードには配下に何個のノードがあるかをカウントした値を格納しておき、どのパスを辿るかを決定するのに使用する。この情報はノード(つまり新たなデータ)を追加したとき、接続される上位ノード群だけを修正すればよいので O(log n) の時間で済む。また、木の回転はそれに関わるノード群だけに影響する。
別の単純な戦略として、ハッシュテーブルのようなコンセプトに基づくものがある。データが取りうる値の範囲が予め分かっている場合、それを h 個の部分に分け、h 個の格納場所を設定する。