1

先日、Javaで基数ソートの実装を作成することにしました。基数ソートは O(k*N) であるはずですが、各桁を 1 つの数値に分解するプロセスのために、最終的に O(k^2*N) になりました。前の数字を修正 (%) し、10 で割って後続の数字を削除することで、各数字を分解しました。これを行うためのより効率的な方法があるかどうか教授に尋ねると、彼はビット演算子を使用すると言いました。さて、私の質問は次のとおりです。Javaで各数値を分解するのに最も速い方法はどれですか。1）上記の方法。2) 数値を文字列に変換し、部分文字列を使用します。3) ビット操作を使用します。

3）の場合、それはどのように機能しますか？

4

2 に答える 2

3

ヒントとして、コンピューターは10進数よりも2進数の算術をより適切に処理するため、10以外の基数を使用してみてください。

  • x>>> nはx/2nと同等です
  • x＆（2 n -1）はx％ 2nと同等です

ちなみに、Javaの>>は符号拡張を実行しますが、これはおそらくこの場合は必要ないことです。代わりに>>>を使用してください。

于 2008-12-01T17:46:59.057 に答える
2

Radix_sort_(Java)

これを行うコード行。

int key = (a[p] & mask) >> rshift;

ビット操作部です。

&ビットごとの AND を実行する演算子で>>あり、右シフトです。

于 2008-12-01T17:35:20.377 に答える