圖說演算法使用JavaScript(十五)

7-2氣泡排序法

氣泡排序法又稱為交換排序法，是由觀察水中氣泡變化構思而成，原理是由第一個元素開始，比較相鄰元素大小，如果大小順序有誤，則對調後在進行下一個元素的比較，就彷彿氣泡逐漸由水底逐漸升到水面上一樣。如此掃描過一次之後就可確保最後一個元素是位於正確的順序。接著再逐步進行第二次掃描，直到完成所有元素的排序關係為止。

以下排序我們利用55、23、87、62、16的排序過程，您可以清楚知道氣泡排序法的演算流程：

由此可知5個元素的氣泡排序法必須執行5-1次掃描，第一次掃描需比較5-1次，共比較4+3+2+1=10次。

JS               bubble.js

var data=[16, 25, 39, 27, 8 ,45, 63];   
//原始資料
console.log('氣泡排序法：原始資料為：');
for (i=0; i<8; i++) 
	process.stdout.write(data[i]+' ');

console.log();

for (i=7; i>0; i--) {    //掃描次數
	for (j=0; j<i; j++) {
		if(data[j]>data[j+1])  {     
		//比較，交換的次數
			temp=data[j];
			data[j]=data[j+1];      
			//比較相鄰兩數，如果第一數較大則交換
			data[j+1]=temp;
		}
	}
	process.stdout.write('第 ' +(8-i)+ ' 次排序後的結果是：')    
	//把各次結果掃描出來
	for (j=0; j<8; j++) process.stdout.write(data[j]+' ');
		console.log();
}
console.log('排序後結果為：');
for (j=0; j<8; j++) process.stdout.write(data[j]+ ' ');
console.log(); 

PHP          buble.php

$data = array("16","25","39","27","8","45","63");
//原始資料
echo "原本陣列是：";
arr_print($data);
echo "<br><br>";

$count=count($data);
for ($i=$count-1; $i>0; $i--){
	//掃描次數
	for ($j=0; $j<$i; $j++){
		//比較，交換的次數
		if ($data[$j]>$data[$j+1]){
			$temp=$data[$j];
			$data[$j]=$data[$j+1];
			//比較相鄰兩數，如果第一數較大則交換
			$data[$j+1]=$temp;
		}

	}
	$time=7-$i;
	echo "第{$time}次";
	arr_print($data);
	echo "<br>";
}
echo "<br><br>";
echo "排完陣列是：";
arr_print($data);

function arr_print($arr){
	foreach ($arr as $key => $value) {
		echo $value." ";
	  	echo "--";
	}
}

7-3選擇排序法

選擇排序法Selection Sort也算是枚舉法的應用，概念就是反覆從未排序的數列中取出最小的元素，加入到另一個數列，結果即為已排序的數列。選擇排序法可使用兩種方式排序，一圍在所有的資料中，當由大至小排序時，則將最大值放入第一位置；若由小至大排序時，則將最大值放入為至末端。例如一開始在所有的資料中挑選一個最小項放在第一個位置(假設是由小到大)，再從第二筆開始挑選一個最小項放在第2個位置，依樣重複，直到完成排序為止。

以下利用55、23、87、62、16數列的由小到大排序過程，來說明選擇排序法的演算過程：

JS          select.js

var showdata=(data)=>   {
	for (k=0; k<8; k++){
		process.stdout.write(data[k]+' ');
	}
}

var select=(data)=> {
	for(i=0; i<7; i++) {
		smallest=data[i];
		index=i;
		for (j=i+1; j<8; j++) {
			//由i+1比較起
			if (smallest>data[j]) {
			//找出最小元素
			smallest=data[j];
			index=j;	
			}	
		}
	tmp=data[i];
	data[i]=data[index];
	data[index]=tmp;
	console.log();
	process.stdout.write('第'+(i+1)+"次排序結果： ");
	showdata(data);
	}
}

data=[63,25,39,27,12,8,45,16];
process.stdout.write('原始資料為：');
for (i=0; i<8; i++) process.stdout.write(data[i]+' ');
	console.log();
	console.log("----------------------------");
	select(data);
	console.log();
	console.log("----------------------------");
	process.stdout.write("排序後資料");
for (i=0; i<8; i++) process.stdout.write(data[i]+'  ');
	console.log();
	console.log("----------------------------"); 

PHP          select.php

$data = array("16","25","39","27","8","45","63");
//原始資料
echo "原本陣列是：";
arr_print($data);
echo "<br><br>";

$count=count($data);

for ($i=0; $i<$count-1; $i++) {
	$smallest=$data[$i];
	$index=$i;
		for ($j=$i+1; $j<$count; $j++) {
					//由i+1比較起
			if($smallest>$data[$j]){
					//找出最小元素
				$smallest=$data[$j];
				$index=$j;
			}
		}
	$tmp=$data[$i];
	$data[$i]=$data[$index];
	//兩個交換
	$data[$index]=$tmp;
	//把$tmp換回來
	$num=$i+1;
	echo "第{$num}次排序結果：";
	arr_print($data);
	echo "<br>";
	
}

echo "<br><br>";
echo "排完陣列是：";
arr_print($data);

function arr_print($arr){
	foreach ($arr as $key => $value) {
		echo $value." ";
	  	echo "--";
	}
}