-
- とりうる値が既知のK通りである時O(N+K)
- 直感的な実装: K個のリストを用意しておいて出現したものをそこに入れていく
- 特殊ケースとしてN通りである時、それぞれ1回しか出現しないのでサイズNの配列を用意すれば良い、O(N)
- 分布数えソート、計数ソート
- ソート対象の値だけをソートする時の実装方法の一つ
- 各値の出現回数を数える
- 中身が同一な可変長リストを実際にメモリにもたなくても「値がiのものがni個ある」とわかれば十分なので
- objをobj.xによってソートするような場合はobj.xが同一でもobjは同一ではないのでこの方法はできない
- 値が一定の範囲外なら無視して良いケース
- 0以上の値のソートでMをこえてたらMとみなして良い、など
- 範囲外の値を丸めた後はとりうる値が一定個になる ABC023D
- とりうる値が既知のK通りである時O(N+K)
-
- 桁にわかれてる値に対して下位の桁からソートをする
- 桁数をkとしてO(kN)
- 各桁に出現しうる値をdとした時にd^kがある程度小さければ(10^6くらい)バケットソートでよい
- 値の範囲があまり大きいと(Nくらい)、桁数kがlogNで結局O(NlogN)になってしまう
-
- ほとんど整列されてるデータに対してO(N)