アルゴリズムをかじります:並べ替えとJavaScriptは実現します.

2435 ワード

正規化を学ぶ前に、分割法を理解する必要があります.それはつまり、分割モードを適用しているからです.(基本的な定義は「アルゴリズム導論」から抜粋する)
一、分治法
1、思想:元の問題をいくつかの規模が小さいが、元の問題に似たサブ問題に分解し、再帰的にこれらのサブ問題を解いて、これらのサブ問題の解決を統合して元の問題の解決を確立する.
2、3つのステップ分割法は、各層の再帰時に、3つのステップがあります.(1)分解:元の問題を分解していくつかのサブ問題に分解し、これらのサブ問題は元の問題の規模が小さい例です.例えば、クラス全員が勝手に一列に並んでいます.この時、背の低い順は乱れています.今は身長順に並べば、問題を前半を身長順に並べて、後半も身長順に二つの問題に分解できます.また、**のいくつかは、サブ問題が必ずしも2つではないことを示しています.2つならば、並べ替えとなります.(2)これらのサブ問題を解決し、再帰的に各サブ問題を解決する.しかし、サブ問題の規模が十分小さい場合は、直接に解決する.例えば、前半と後半の並べ替えのサブ問題をそれぞれ解決します.例えば、前半に並べ替えて、また問題を前の1/4に分解して並べ替えて、1/4から1/2の部分に並べ替えて、この2つの問題を解決した後に合算アルゴリズムを採用して合算して前の半分の身長の並べ替えを得ます.事実上、前の1/4に並べ替えてまた再度分解することができます…まで分解して単一の学友の並べ替えになって、この時更に分解する必要はなくて、並べ替えた後の序列は彼自身です.(3)これらのサブ問題を統合して、元の問題に解決する.**.たとえば、**は、統合アルゴリズムを用いて、最初の半分の列と後の半分の列を統合し、全員の身長ランキングを取得する.
二、並べ替え
正規並べ替えは完全に分割モードに従う.
1、ステップ:(1)分解:並べ替えられるn個の要素のシーケンスを分解して、それぞれn/2個の要素の2つのサブシーケンスにする.(2)解決策:2つのサブシーケンスは、規格化された順序付けを使用して再帰的に並べ替えられる.(3)統合:並べ替えられた2つのサブシーケンスを結合して、並べ替えられた答えを生成します.
2、キー:「マージ」ステップで並べ替えられた2つのシーケンスのマージ.
3、合併アルゴリズム:この時の前半と後半はそれぞれ順序を決めて、一番低いのは各部分の一番前にあると仮定します.この時は二つの並べ替えを組み合わせるだけで、クラス全員の並べ替えができます.連結アルゴリズムは同様である:(1)前の半分の列が一番低いのは甲で、後の半分の列の中で一番低いのは乙で、甲と乙を比較して、両者の中で一番低いのはaと命名して、aを合併の隊列の中に置いて、この時に合併の隊列の中でa一人だけあります.(2)前の半分の列と後の半分の列の中で一番低い人を再度比較して、今のbが一番低いと仮定して、bを合併の列の中のaの後に置いて、この時に合併の隊列はa、bの2人がいます.(3)…(4)前の列または後の列に人がいない.前の半分の列がなくなったと仮定して、今の後の半分の列の中で残りの学生はすでに合併した学友より高くて、直接に残りの学生を順次に合併した列の後に並べて、並べ替えは完成します.
三、私のJavaScriptが実現しました.
	function merge_sort(arr) {
			if (arr.length>1) {
				var array=[];
				var l=Math.floor(arr.length/2);
				for (var i = 0; i < l; i++) {
					array.push(arr.pop());
				}
				merge_sort(arr);
				merge_sort(array);
				merge(arr, array);
			}else{
				return arr;
			}
		}
		function merge(arr1,arr2) {
			var arr=[];
			while(arr1.length&&arr2.length){
				if (arr1[0]<=arr2[0]) {
					arr.push(arr1.shift());
				}else{
					arr.push(arr2.shift());
				}
			}
			if (arr1.length) {
				for (var i = 0; i < arr1.length; i++) {
					arr.push(arr1.shift());
				}
			}else if (arr2.length) {
				for (var j = 0; j < arr2.length; j++) {
					arr.push(arr2.shift());
				}
			}
			var l=arr.length;
			for (var i = 0; i < l; i++) {
				arr1.push(arr.shift());
			}
		}
	var a=[11,2,3,445,7,32,71,1,94];
	merge_sort(a);
    console.log(a);
    var b=[94,11];
    merge_sort(b);
    console.log(b);
以上のコードには最適化できるスペースがあります.他の人の実現を比較して、sliceを採用するなら簡単になりそうです.