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

7-4插入排序法

插入排序法insert sort則是將陣列中的元素，逐一與已排序好的資料作比較，如前兩個元素先排好，再將第三個元素插入適當的位置，所以這三個元素仍然是已排序好，接著再將第四個元素加入，重複此步驟，直到排序完成為止。各位可以看做是在一串有序的紀錄R1、R2..Ri，插入新的紀錄R，使得i+1個紀錄排序妥當。

以下利用55、23、87、62、16數列的由小到大排序過程，來說明插入排序法的演算流程。下圖中，在步驟二，以23為基準與其他元素比較後，放到適當位置(55的前面)，步驟三則拿87與其他兩個元素比較後，接著62在比較完前三個數後插入87的前面…，將最後一個元素比較完後即完成排序：

JS          insert.js

let SIZE=8;
	//定義陣列大小
var showdata=(data)=> {
	for (k=0; k<8; k++) {
		process.stdout.write(data[k]+' ');
	}
}

var insert=(data)=> {
	for (i=0; i<SIZE; i++) {
		tmp=data[i];
		//tmp用來暫存資料
		no=i-1;
		while (no>=0 && tmp<data[no]) {
			data[no+1]=data[no];
			//就把所有元素往後推一個位置
			no-=1;
		}
		data[no+1]=tmp;
		//最小的元素放到第一個元素
	}
}
data=[16,25,39,27,12,8,45,63];
console.log('原始陣列是：');
showdata(data);
insert(data);
console.log();
console.log('排序後陣列是：');
showdata(data);

PHP          insert.php

$data=array(16,25,39,27,12,8,45,63);
$count=count($data);

echo "原始陣列：<br>";
showdata($data);

$new_data=insert($data);

echo "<br>排列後的陣列：<br>";
showdata($new_data);

function insert($arr) {
	$count=count($arr);
	//計算陣列大小
	for ($i=0; $i<$count; $i++) {
		$tmp=$arr[$i];
		//用tmp來暫存資料
		$no=$i-1;
		while ($no>=0 && $tmp<$data[$no]){
			$data[$no+1]=$data[$no];
			//就把所有元素往後推一個位置
			$no--;
		}
		$data[$no+1]=$tmp;
		//最小的元素放到第一個元素  
	}
	return $data;
}


function showdata($arr){
	foreach($arr as $key=>$value){
		echo $value."、";
	}
	echo "<br>";
}

7-5謝耳排序法

我們知道如果原始紀錄的鍵值大部分以排序好的情形下，插入排序法或非常有效率，因為它無須做太多的資料搬移動作。[謝耳排序法]是D.L.Shell在1959年7月所發明的一種排序法，可以減少插入排序法中資料搬移的次數，以加速排序進行。排序的原理是將資料分成特定間隔的幾個小區塊，以插入排序法排完區塊內的資料後再漸漸減少間隔的距離。

以下利用63、92、27、36、45、71、58、7數列的由小到大排序過程，來說明謝耳排序法的演算過程。

範例：shell.js>請設計一程式，並使用謝耳排序法來將以下的數列排序：
16,25,39,27,12,8,45,63

JS           shell.js

let SIZE=8;

var showdata=(data)=> {
	for (i=0; i<SIZE; i++) {
		process.stdout.write(data[i]+ ' ');
	}
	console.log();
}

var shell=(data, size)=> {
	k=1;
	//k列印計數
	jmp=parseInt(size/2);
	while (jmp !=0) {
		for (i=jmp; i<size-1; i++) {
			//i為掃描次數 jmp為設定間距位移量
			tmp=data[i];
			//tmp用來暫存資料
			j=i-jmp;
			//以j來定位比較的元素
			while (tmp<data[j] && j>=0) {
				//插入排序法
				data[j+jmp] = data[j];
				j=j-jmp;
			}
			data[jmp+j]=tmp;
		}
		process.stdout.write('第 '+k+' 次排序過程：');
		k=k+1;
		showdata(data);
		console.log('------------------------------------');
		jmp=parseInt(jmp/2);
		//控制迴圈數
	}
}

data=[16,25,39,27,12,8,45,63];
process.stdout.write('原始陣列是：     ');
showdata(data);
console.log('-------------------------------------');
shell(data, SIZE);

PHP            shell.php

$data=array(16,25,39,27,12,8,45,63);
echo "原始陣列：<br>";
print_arr($data);
echo "----------------------------<br><br>";


$size=count($data);
$new_data=shell_sort($data, $size);

echo "<br>排序後的陣列：<br>";
print_arr($new_data);

function shell_sort($arr, $size) {
	$k=1;
	//k列印計數
	$jmp=intval($size/2);
	
	while($jmp!=0) {
		for($i=$jmp; $i<$size-1; $i++) {
			//i為掃描次數 jmp為設定間距位移量
			$tmp=$arr[$i];
			//tmp用來暫存資料
			$j=$i-$jmp;
			//以j來定位比較的元素
			while ($tmp<$arr[$j] && $j>=0) {
				//插入比較法
				$arr[$j+$jmp]=$arr[$j];
				$j=$j-$jmp;
				isset($arr[$j])?$arr[$j]=$arr[$j]:$arr[$j]=null;
				//偵測$arr[$j]的key值是否為正確
				//echo $j."<br>";
			}
			$arr[$jmp+$j]=$tmp;
		}
		echo "第".$k."次排序過程<br>";
		$k++;
		print_arr($arr);
		$jmp=intval($jmp/2);
		//控制迴圈數
	}
	
	return $arr;	
}

function print_arr($arr) {
	foreach ($arr as $key => $value){
		echo $value." ";
	}
	echo "<br>";
}