次の 000111010110 のような 0 と 1 を含むバイナリ値のみのリストがあり、それを次の 000000111111 に並べ替えたい場合、リストのサイズもわかっている場合、これを行う最も効率的な方法は何でしょうか? 現在、リストを最初から最後までトラバースするときに 0 の数をカウントするカウンターを 1 つ持つことを考えています。次に、listSize を numberOfZeros で除算すると、numberOfOnes が得られます。次に、ゼロから始まるリストを並べ替える代わりに、新しいリストを作成することを考えていました。これが最も効率的な方法であることに同意しますか?
3 に答える
1
あなたのアルゴリズムは、古典的なバケットソートアルゴリズムの最も原始的なバージョンを実装しています（そのカウントソート実装）。範囲がわかっていて、（比較的）小さい場合に、数値を並べ替えるのに可能な限り最速の方法です。持っているのは0と1だけなので、バケットソートに存在するカウンターの配列は必要ありません。1つのカウンターで十分です。
于 2012-10-26T16:11:35.877 に答える
0
バケットソートは、見た目どおりのソートアルゴリズムです。
そのような操作が必要だとは思いません。私たちが知っているように、 N*logN よりも高速な並べ替えアルゴリズムはありません。したがって、デフォルトでは間違っています。
そして、あなたがしなければならないのは、あなたが最初に言ったことだけだからです。リストをトラバースして、O(n) の複雑さを与えるゼロまたは 1 を数えるだけです。次に、カウントされたゼロで新しい配列を作成するだけです。始まりに続いてOneが続きます。次に、合計N + Nの複雑さがあり、O（n）の複雑さが得られます。
これは、値が 2 つしかないためです。したがって、クイック ソートも他のソートも、これをより高速に実行することはできません。NLog(n) よりも高速なソートはありません。
于 2012-10-27T03:10:42.587 に答える
0
数値がある場合は、アセンブリ命令ビットスキャン (x86 アセンブリの BSF) を使用してビット数をカウントできます。「ソートされた」値を作成するには、n+1 ビットを設定してから 1 を引きます。これにより、すべてのビットが n+1 ビットの右側に設定されます。
于 2012-10-26T17:38:45.377 に答える