JSはマージソートを実装します-jsチュートリアル-php.cn

JSはマージソートを実装します

不言

リリース： 2018-07-07 17:42:06

オリジナル

2199 人が閲覧しました

この記事では主にマージソートのJS実装を紹介しますので、必要な友達は参考にしてください

再帰を深く理解したことがないからです。その再帰処理は非常に抽象的であり、メモリスタックの戻り処理を明確に解析することはできません。偶然、再帰に関するブログ記事を見つけました (技術的な問題については、さらに詳しく調べる必要があると言わざるを得ません)。再帰プロセスのメモリスタック分析について突然啓発されました。分析プロセスは以下のとおりです。次の図は、再帰全体を正確に示しています。この過程で、将来単一の再帰の問題が発生した場合は、この方法を使用してそれを分析できます (複数の再帰の場合は、マージソートで 2 つの再帰を描画しようとしますが、きれいに入力する方法は本当にないので、あきらめてください...)

本題に戻り、マージと並べ替えを分析しましょう。

JSはマージソートを実装しますマージソート

マージソートは、分割統治の考え方を採用しています。1 つ目は、各配列の要素が 1 つだけになるまで配列を 2 つの小さな配列に繰り返し分割する「征服」です。最小の配列から順に各ペアをマージして、元の配列サイズにマージすることを以下に示します。

実際に「統治」していることがわかります。すでに順序付けされた配列をマージして、より大きな順序付けされた配列を作成することを意味します。では、すでにソートされた配列をより大きなソート配列にマージするにはどうすればよいでしょうか?非常に簡単です。一時配列 C を作成し、A[0]、B[0] を比較し、小さい方の値を C[0] に代入し、A[1] と B[0] (または A[0]、 B [1])、A と B の両方を通過するまで、小さい方の値を C[1] に入れます。配列 A と B は一度だけ走査する必要があるため、2 つの順序付けされた配列をソートする時間計算量は O(n) であることがわかります。

JSはマージソートを実装しますそして、「分割」とは、各配列に 1 つの要素だけが残るまで、元の配列を 2 つの部分に順番に分割することです。1 要素の配列は自然に整うので、「修復」のプロセスを開始できます。

時間計算量分析: 分割プロセスには 3 つのステップが必要です: log8 = 3、各ステップは 8 つの要素を 1 回走査する必要があるため、合計 8 つの要素を 8log8) 命令を実行する必要があります。その後、n 要素の時間計算量は次のようになります。ああ(nlogn)。

このコードは 2 つの再帰を使用していますが、非常に抽象的で理解するのが難しく、それを理解するのに 1 ページ分のスタック呼び出し図が必要でした (あまりにも乱雑なので投稿しません)。

// A C++ program to demonstrate working of recursion
#include<bits>
using namespace std;
void printFun(int test)
{
    if (test <p> 以上がこの記事の全内容です。その他の関連コンテンツについては、PHP 中国語 Web サイトをご覧ください。 </p>
<p>関連する推奨事項: </p>
<p></p>JS は Hill ソートを実装します<p></p>
<p><a title="JS实现希尔排序" href="//m.sbmmt.com/js-tutorial-406221.html" target="_blank"></a>Jquery は読み込み遷移マスクを追加します<br></p>
<p></p></bits>

ログイン後にコピー

以上がJSはマージソートを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。