学習アルゴリズム -  マージソート

以前は、1 , 566 , 915 , 000円の外観を有していた.
しかし、その最悪のシナリオはO(N)であった.そして、私はあなたにマージソートである配列をソートするより洗練された、より速いアルゴリズムを約束しました.
─
それで、どのように我々は要素のリストになるとソートのための時間を節約できますか?答えは分割し、征服することです.私は、あなたがこのアルゴリズムでバイナリ検索を知っている必要があると仮定します.あなたに全体計画の大きな絵をあげましょう.第1に、私たちは、サイズNの配列を持ちます、そして、私たちはそれを呼びます.次に、2つの配列をソートします.最後に、配列Aでソート順にマージします.
─
─
残念ながら、マージソートを使用するには、この悪循環的な概念、いわゆる再帰を知っている必要があります.一言で言えば、再帰はそれ自体を呼び出す関数呼び出しです.以下のコードを見てみましょう.
─
─
関数callper me ( arg )は自身を呼び出し、argを出力する.この場合どうなるのですか.それは、私自身をブラックホールのように「私は私を呼んでいる」と無限に印刷することを呼びます.これは、エラーの悪名、スタックオーバーフロー、これは文字通りの関数呼び出しスタックされ、プログラムは、これらの呼び出しを格納するメモリ空間を使用するので、エラーをスローします.それで、我々がする必要があるすべては若干の点でこの再帰を終えさせることです、それをするために、我々は再帰を終える状態を必要とします、我々はそれをベースケースと呼びます.
─
ベースのケースでこの再帰を止めさせてください.CallSum ME関数は1つ以上の引数を取っています.Iは1つごとに実行ごとにインクリメントされます.
─
─
─
─
私は、我々が現在クラックを得る準備ができていると仮定します.このソートされていない配列Aを次のようにします.
─
先に計画段階で述べたように、左半分(L)と右半分(R)の配列をコピーします.
─
─
分割できないまで再帰的に配列を半分にします.先に説明したように、いくつかの点で再帰を停止させるための基本的なケースが必要です.配列が1つになるまでは配列が1になります.
─
─
上記のコードの結果、配列はこのようになります.なお、ハルディング処理の各レベルは同時に発生するので、この場合、アレイ長を8にするために4ステップをとった.
─
今、要素をソートするために、配列Aにマージしてソートするときです.最初のものは小さいものです、より大きいものは次に来ます.マージとソートの実装は、要素が配列Aに戻されると、インデックスは次の要素に移動します.
─
最後に残っているのは、LまたはRから配列Aに移動されていない要素を挿入することです.つまり、LとRの長さが異なるとき、つまり、Aの長さが7のような奇数であるときに起こります.
─
マージのプロセスはこのようになります.
─
─
─
このアルゴリズムo(n log n)の分割計算量とconphase位相(halving array)の時間複雑さを考慮した.しかし、マージと並べ替えのフェーズについてはどうですか?それは並べ替えとマージする各配列をループします.最悪の場合、他のケースは問題ではないので、時間の複雑さはO(n)である.
─
どのように多くのメモリ空間のマージソートを使用する?たくさん!これは、配列の半分をコピーし、要素の数に応じて余分なスペースを意味します.したがって,マージソートの空間的複雑さはo(n)である.挿入ソートと比較して、マージソートO ( n )>挿入ソートO ( 1 )です.
それは最後まで長い旅でした、私はあなたが現在概念の良い把握を持っていることを望みます.