新しいソートアルゴリズムの発明から始まる

このような単純なアルゴリズムは、先代のエンジニアが考え出したものであるに違いありません。初心者であっても、偶然これを発見することは珍しくありません。私は郭小思の例に倣って、他人の業績を盗用するつもりはありません。結局のところ、これは単なるナンセンスな記事の連続であり、本当に価値のある部分はそこから生じる疑問です。

マージ アルゴリズムでは、2 つのシリーズをマージするには m+n のスペースが必要であり、ソート後にキューをコピーし直す必要があります。私のバージョンのアルゴリズムでは、最初に同じ長さのメモリ片を適用し、その後、書き戻すことなくデータを順番に書き込むことができます。一度書き込んだ後、2 つのメモリ片を交換して書き込みを続けます。これにより、書き込みオーバーヘッドが半分に削減され、スペース要求が繰り返される問題を回避できます。

スワップの数によって、ソートが完了したときに正しいデータがどのメモリに書き込まれるかが決まります。

スワップ回数が偶数の場合は、元のメモリに書き込みます。

スワップ数が奇数の場合は一時メモリに書き込みます。

スワップの数が奇数の場合、データは元のメモリにもコピーする必要があります。ただし、2回ずつ交換する場合は、比較データが1つだけなので、追加のメモリは必要なく、単純な交換で十分です。奇数回の場合には、最初に比較を行い、その後、偶数回の比較を行います。したがって、このコードはアルゴリズムの主要部分の前に存在します。

 int temp = len、i = 0、サイズ = 1;
整数l1p、l1end、l2p、l2end;
 int *テンプレートリスト、*リストb;
 printarr(リスト、長さ);
長さ<=1の場合{
戻る;
 }
私 = 0;
 //スワップタイムを計算する 
 (temp){の間
    温度 = 温度>>1;
    私は++;
 }
もし（i%2）{
 (i=0;(i+1)<len;i+=2)の場合{
 (リスト[i]>リスト[i+1])の場合{
            temp = リスト[i];
            リスト[i] = リスト[i+1];
            リスト[i+1] = temp;
        }
    }
    サイズ = 2;
    printarr(リスト,長さ);
 }

このコードは目的を果たしますが、非常に厄介な点があります。交換回数を計算する場合、O(n) ループを使用して回数を取得します。ちょっと非効率な気がします。

実際には、長さの最初の桁だけが重要です。その桁によってスワップの回数が決まるからです。

そこで、もっと速い方法を探し始めました。英語では、この問題は「整数の 2 を底とする対数を求める」と呼ばれています。この問題について説明しているスタンフォードのページは、次のとおりです: http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

残念ながら、この問題に対する最速の解決策は、現在、バイナリ検索に基づく logN のみです。しかし、N を logN に減らすのは、数字の長さに対して少しやり過ぎなので、O(1) メソッドを見つけることは依然として理にかなっています。

このアイデアの理由は、ビット操作の世界では、いくつかのアルゴリズムが非常に魅力的であるからです。

例えば

x&(x-1)

Xの右端から連続する0は1で埋めることができる

x&(-x)

右端の1は別々に描くことができる

等

したがって、私たちの問題は O(1) を使用しても解決できると常に感じています。

しかし、これらの単純で使いやすい魔法のトリックは、数字の右側にのみ関係しているようです。右側のビットを操作するには、1 や FFFFFF などの既知の数字を使用できますが、その数字の log の底 2 の整数を知らない限り、左側のビットを右側のビットと同じように操作することはできません... 左端の 0 を埋める方法があれば解決策を得ることができますが、この一見単純な問題は実際には今日まで解決できない問題であり、新しいバージョンの CPU に特別な問題に対応する命令がない限り、logN 未満のステップでこの問題を解くことは不可能と思われます。

しかし、私たちのアプリケーションではこれで終わりではありません。最終的な目標は、ビットが奇数の位置にあるか偶数の位置にあるかを知ることだからです。つまり、問題は次のようになります。

左端の 1 が偶数の位置にある場合は、偶数回のスワップが必要です。奇数の位置にある場合は、奇数回のスワップが必要です。

この方法で問題はうまく解決されたようです。これが書き直されたコードです

int temp = len-1、i = 0、サイズ = 1;
整数l1p、l1end、l2p、l2end;
 int *テンプレートリスト、*リストb;
 printarr(リスト,長さ);
長さ<=1の場合{
戻る;
 }
 // 最上位ビットが奇数位置にある場合にのみ、スワップ時間を計算します 
 ((temp&0xaaaaaaaa)<(temp&0x55555555)){の場合
(i=0;(i+1)<len;i+=2)の場合{
 (リスト[i]>リスト[i+1])の場合{
            temp = リスト[i];
            リスト[i] = リスト[i+1];
            リスト[i+1] = temp;
        }
    }
    サイズ = 2;
    printarr(リスト,長さ); }

0xAAA...AA は偶数ゲート、0x555...55 は奇数ゲートと呼ぶことができます。*** ビットが偶数の位置にある場合、偶数ゲートと奇数ゲートの結果は、奇数ゲートと奇数ゲートの結果よりも大きくなければなりません。逆もまた同様です。この問題は解決できます。

オリジナルリンク: http://my.oschina.net/u/1167335/blog/142894