O(n) sort algorithm
O(n)のソートアルゴリズムは使用個所が限られるが、使おうとすれば結構使えると思う。
- メリットはもちろん処理速度が極速と言うこと。
- デメリットはその分メモリを喰うこと。
この二つの関係をなんたらの法則って聞いた事あったけど・・・なんでしたっけ?
さて、我らが
google:Wikipadia*1
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88
によると
google:バケットソート
google:基数ソート
google:逆写像ソート
だそうだ。そしてgoogle:計数ソート]([google:分布数えソート)がある。
ちなみに分布数えソートはdkutil_cに実装してある。*2
*1:本当はgoogle:Wikipedia padiaでもしっかり検索されるから面白い