アルゴリズム学習---並べ替え(一)

23104 ワード

先端学習データ構造ソートアルゴリズム

このメモで泡立て並べ替え、並べ替え、並べ替え、並べ替え、快速並べ替えの実現コードを記録して、自分が後で調べるために.

発泡体の並べ替え:安定した並べ替え;元の位置に並べ替えて、空間複雑度O(1)、平均時間複雑度O(n^2)

function mpSort(arr) {
	for (let i=0;i<arr.length;i++) {
		//    ，          ，flag   true，        
		let flag = false;
		for (let j=0;j<arr.length - 1 - i;j++) {
		//              ，    
			if(arr[j]>arr[j+1]) {
				let temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				flag = true
			}
		}
		if(!flag) {
			break
		}
	}
	return arr
}

挿入順序:安定した並べ替え;元の位置に並べ替えて、空間複雑度O(1)、平均時間複雑度O(n^2)

function crSort(arr) {
	//        ，        ，       
	for(let i=1;i<arr.length;i++) {
	//                                 
		let value = arr[i];
		let j = i - 1;
		for(;j >= 0;j--) {
		//       ，       
			if(value < arr[j]) {
				arr[j + 1] = arr[j]
			} else {
				break
			}
		}
		arr[j + 1] = value; 
	}
	return arr
}

正規並べ替え:安定した並べ替え;元の場所ではなく、空間複雑度O(n)、平均時間複雑度O(nlogn);思想を分治し,再帰方法を定める.

function mergeSort(arr) {
	//                      
	if(arr.length < 2) {
		return arr
	}
	//    
	let mid = Math.floor(arr.length / 2);
	//slice                         （   mid）
	let leftArr = arr.slice(0,mid);
	let rightArr = arr.slice(mid);
	//    ，    ，      
	return mergeSort_s(mergeSort(leftArr),mergeSort(rightArr));
}
//    
function mergeSort_s(leftArr,rightArr) {
	let result = [];
	//          ，      ，       ，    -1
	while(leftArr.length && rightArr.length) {
		if(leftArr[0] > rightArr[0]) {
			//shift()            ，            
			result.push(leftArr.shift())
		} else {
			result.push(rightArr.shift())
		}
	}
	//        ，         ，                    result
	while(leftArr.length > 0) {
		result.push(leftArr.shift())
	}
	while(rightArr.length > 0) {
		result.push(rightArr.shift())
	}
	return result
}

快速並べ替え:不安定な並べ替え;元の場所に並べ替えて、空間複雑度O(1)、平均時間複雑度O(nlogn);思想を分治し,再帰方法を定める.
PS:快速並べ替えの考え方は一致していますが、いくつかの書き方があります.ここで書くのが一番いいです.欠点は単独で空間を開拓しなければならないので、もとの場所の順序付けをやり遂げていません.
書き方一:元の場所ではなく並べ替え

function quickSort(arr) {
	if(arr.length < 2) {
		return arr
	}
	let mid = Math.floor(arr.length / 2);
	let leftArr = [];
	let rightArr = [];
	//           ，           
	let pivot = arr.splice(mid,1)[0];
	for (let i = 0;i < arr.length;i++) {
		if(arr[i] > pivot) {
			rightArr.push(arr[i])
		} else {
			leftArr.push(arr[i])
		}
	}
	//         ，        ，             
	return quickSort(leftArr).concat(pivot, quickSort(rightArr))
}

最近いくつかの文章を読んで、ようやくこのような書き方を理解しました.実は、快速に並べられた考え方はその通りです.基準点より大きいのをその右に置いて、基準点より小さいのをその左側に置いて、このように繰り返してその左右の配列に戻します.考え方はこうですが、書き方はいろいろあります.ここで使っているのは前後の指針です.書き方二:もとの場所で並べ替えます.

function quickSort(arr,left,right) {
	if(left > right) {
		return;
	}
	//        （     ）
	let i = left;
	let j = right;
	let base = arr[left];
	while(i < j) {
		//       ，          
		while(i < j && arr[j] >= base) {
			j--
		}
		//      ，          ，         
		while(i < j && arr[i] <= base) {
			i++
		}
		if(i < j) {
			let temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	//          ，    ，     i,j             
	arr[left] = arr[i];
	arr[i] = base
	//                 
	quickSort(arr,left,i-1);
	quickSort(arr,i+1,right)
}

補足:一番長くていくつかの並べ替えアルゴリズムを勉強しましたが、いずれも特殊で、データに対して厳しい要求があります.しかし、条件を満たすと、時間の複雑さはO(n)に達することができます.
1.桶の並べ替え:例を挙げる.一群の金額が0-50の注文書で並べ替えられます.いくつかの桶に分けられます.
制限条件:1.分けられた桶は天然の大きさの関係があります.2.各バケツのデータ量の差は大きすぎてはいけません.
2.カウント順:または例を挙げます.10万人の受験生を並べ替えて、私達は総合得点範囲を0-600に設定します.そこで、601個の桶に分けて、点数が基準値以下の受験生を対応する桶に入れます.桶内のデータは並べ替えなくてもいいです.そして順番にデータをバケツから取り出して配列に預けます.ここにはすごい考えがあります.後でコードを補充します.
制限条件:1.データ範囲は大きすぎるべきではない.2.正の整数だけを並べ替えることができます.正の整数(たとえば小数)でない場合は、カウントで並べ替える必要があります.データは相対的な大きさが変わらない場合、正の整数に変換されることを保証します.
3.基数並べ替え:例を挙げ続けます.電話番号を並べ替えます.電話番号の桁数は11桁なので、この時は明らかにバケツの並べ替えと計数の並べ替えには不向きです.基数並べ替えの操作は簡単に言えば、電話番号の相対的な桁数を比較して、例えば末位から比較して、そして並べ替えて、10位に対して第1位まで並べ替えて、私達は全体の11桁の数字を複数の桁の数字に対して並べ替えて比較して、上の数え方と桶の並べ替えの条件に合致します.PS:並べ替えたいデータのセットの桁数が等しくない場合はどうすればいいですか?たとえば単語なら、私たちは0を一桁で補う方法を採用することができます.制限条件:1.比較するデータのセットは、独立したビットに分割され、ビットとビットとの比較可能な関係が必要です.2.ビットの範囲が大きすぎてはいけません.大きすぎると線形ソートの制限条件が満たされなくなります.時間の複雑さがO(n)の効果に達しません.
私の理解では、この3つの並べ替えは、実は前に述べた基礎的な並べ替えに基づいています.樽の並べ替えは、複数の桶に分割されたステップを使っています.ですから、これらのアルゴリズムの書き方は丸暗記しなくてもいいです.一番大切なのは彼の考えです.例えば、電話番号の並べ替えに対して、これらの並べ替え思想を教えてくれない時は、ただ早送りを知っているだけかもしれませんが、元素の長さがそんなに大きいので、どの基礎を使って並べ替えても不合理です.この中には数え方だけが巧みな新しい書き方をしています.後でコードを追加します.

C言語は簡単な通信録を実現します.