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

7-6合併排序法

合併排序法(Merge Sort)工作原理乃是針對已排序好的二個或二個以上的數列，經由合併的方式，將其組合成一個大的且已經排序好的數列。步驟如下：

1.將N個長度為1的鍵值成對地合併成N/2個長度為2的鍵值組。
2.將N/2個長度為2的鍵值組成對地合併成N/4個長度為4的鍵值。
3.將鍵值不斷地合併，直到合併成一組長度為N的鍵值組為止。

以下利用38、16、41、72、52、98、63、25數列的由小到大排序過程，來說明合併排序法的基本演算流程：

上面展示的合併排序法例子是一種最簡單的合併排序，又稱為2路(2way)合併排序，主要概念是把原來的檔案視作N個已排序妥當且長度為1的數列，再將這些長度為1的兩兩合併，結合成N/2個已排序妥當且長度為2的數列；同樣的作法，再依序兩兩合併，合併成N/4個排序妥當且長度為4的數列….，以此類推，最後合併成一個已排序妥當且長度為N的數列。步驟整理如下：

1.將N個長度為1的數列合併成N/2個已排序妥當且長度為2的數列。
2.將N/2個長度為2的數列合併成N/4個已排序妥當且長度為4的數列。
3.將N/4個長度為4的數列合併成N/8個已排序妥當且長度為8的數列。
4.將N/2i-1個長度為2i-1的數列合併成N/2i個已排序妥當的數列。

範例：merge.js>請設計一程式，並使用合併排序法來排序。

JS             merge.js

//合併排序法(Merge Sort)

//99999為串列1的結束數字不列入排序
list1=[20,45,51,88,99999];
//99999為串列2的結束不列入排序
list2=[98,10,23,15,99999];
list3=[];

for (i=0; i<list1.length-1; i++) process.stdout.write(list1[i]+' ');
console.log();
for (i=0; i<list2.length-1; i++) process.stdout.write(list2[i]+' ');
console.log();

var merge_sort=()=> {

	//先使用選擇排序將兩數列排序，再做合併
	select_sort(list1, list1.length-1);
	select_sort(list2, list2.length-1);
	console.log();
	process.stdout.write('第1組資料的排序結果：');
	console.log();
	for (i=0; i<list1.length-1; i++) process.stdout.write(list1[i]+' ');
	console.log();
	process.stdout.write('第2組資料的排序結果：');
	console.log();
	for (i=0; i<list2.length-1; i++) process.stdout.write(list2[i]+' ');
	console.log();
	
	for (i=0; i<60; i++) process.stdout.write('=');
	console.log();
	
	My_Merge(list1.length-1, list2.length-1);

	for (i=0; i<60; i++) process.stdout.write('=');
	console.log();
	
	process.stdout.write('合併排序法的最終結果： ');

	for (i=0; i<list1.length+list2.length-2; i++)
		process.stdout.write(list3[i]+ ' ');
}

var select_sort=(data, size)=> {
	for (base=0; base<size-1; base++) {
		small=base;
		for (j=base+1; j<size; j++) {
			if (data[j]< data[small]) small=j;
		}
		temp=data[small];
		data[small]=data[base];
		data[base]=temp;
	}
}

var My_Merge=(size1, size2)=> {
	index1 = 0;
	index2 = 0;

	for (index3=0; index3<list1.length+list2.length-2; index3++) {
		if (list1[index1] < list2[index2]) {
			list3.push(list1[index1]);
			index1 +=1;
			process.stdout.write('此數字'+ list3[index3]+ '取自於第1組資料');
		}
		else {
			list3.push(list2[index2]);
			index2 +=1;
			process.stdout.write('此數字'+ list3[index3]+ '取自於第2組資料');
		}
		console.log();
		process.stdout.write('目前的合併排序結果： ');
		for (i=0; i<index3+1; i++) process.stdout.write(list3[i]+ ' ');
		console.log();
	}
}

//主程式開始
merge_sort();

PHP           merge.php

$list1=array(88,45,51,20,99999);
$list2=array(98,10,23,15,99999);
$list3=array();

merge_sort($list1, $list2, $list3);

function merge_sort($data1, $data2, $data3) {
	
	echo "第1組原始陣列：";
	print_arr($data1);
	echo "第2組原始陣列：";
	print_arr($data2);
	echo "第3組原始陣列：";
	print_arr($data3);
	echo "<br>";
	
	echo "第1組資料的排序結果：";
	print_arr(select_sort($data1));
	echo "第2組資料的排序結果：";
	print_arr(select_sort($data2));

	for ($i=0; $i<60; $i++){
		echo "=";
	}
	$sort_data1=select_sort($data1);
	$sort_data2=select_sort($data2);

	print_arr(My_Merge($sort_data1, $sort_data2));
}

function select_sort($data) {
	$size=count($data);

	for ($base=0; $base<$size-1; $base++) {
			$small=$base;
			for ($j=$base+1; $j<$size; $j++) {
				if ($data[$j] < $data[$small]) $small=$j;
			}
			$temp=$data[$small];
			$data[$small]=$data[$base];
			$data[$base]=$temp;
		}
		return $data;
}

function  My_Merge($data1, $data2) {
	$index1=0;
	$index2=0;
	$size1=count($data1);
	$size2=count($data2);
	$data3=array();

	for ($index3=0; $index3<$size1+$size2-2; $index3++) {
		if ($data1[$index1] < $data2[$index2]) {
				//array_push($data3, $data1[$index1]);
				$data3[]=$data1[$index1];
				$index1 ++;
				echo "<br>此數字".$data3[$index3]."取自於第1組資料";
		}else{
				//array_push($data3, $data2[$index2]);
				$data3[]=$data2[$index2];
				$index2 ++;
				echo "<br>此數字".$data3[$index3]."取自於第2組資料";
		}

		print_arr($data3);
		
		}
		return $data3;
}

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

7-7快速排序法

快速排序法(Quicksort)是由C.A.R.Hoare所發展的，又稱分割交換排序法，是目前公認最佳的排序法，也是使用分治法(Divide and Conquer)的方式，先是資料中找到一個隨機設定虛擬中間值，並依此中間值的資料將所有打算排序的資料分為兩部分。其中小於中間值的資料放在左邊，而大於中間值的資料放在右邊，再以同樣的方式分別處理左右兩邊的資料，直到排序完為止。操作與分割步驟如下：

假設有n筆R1、R2、R3…Rn紀錄，其鍵值為K1、K2、K3…Kn：
1.先假設K的值為第一個鍵值。
2.由左向右找出鍵值Ki，使得Ki>K。
3.由右向左找出鍵值Kj，使得Kj<K。
4.如果i<j，那麼Ki與Kj交換，並回到步驟2。
5.i>=j則K與Kj交換，並以j為基準點分割成左右部分。然後再針對左右兩邊進行步驟1至5，直到左半邊鍵值=右半邊鍵值為止。

JS               quick.js

var inputarr=(data, size)=> {
	for (i=0; i<size; i++) data[i]=Math.floor(Math.random()*100)+1;
}

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

var quick=(d,size,lf,rg)=> {
	//第一筆鍵值為d[lf]
	if (lf<rg) {
		//排序資料的左邊與右邊
		lf_idx=lf+1;
		while (d[lf_idx] < d[lf]) {
			if (lf_idx+1 > size) break;
			lf_idx +=1; 
		}
		rg_idx=rg;
		while (d[rg_idx] > d[lf]) rg_idx -=1;
		while (lf_idx < rg_idx) {
			tmp=d[lf_idx];
			d[lf_idx]=d[rg_idx];
			d[rg_idx]=tmp;
			lf_idx +=1;
			while (d[lf_idx] < d[lf]) lf_idx +=1;
			rg_idx -=1;
			while (d[rg_idx] > d[lf]) rg_idx -=1;
		}
		tmp=d[lf];
		d[lf]=d[rg_idx];
		d[rg_idx]=tmp;

		for (i=0; i<size; i++) process.stdout.write(d[i]+ ' ');
		console.log();
		quick(d,size,lf,rg_idx-1);
		//以rg_idx危機點分成左右兩半以遞迴方式
		quick(d,size,rg_idx+1,rg);
		//分別為左右兩半進行排序直至完成排序
	}
}

var data=new Array(100);
for (i=0; i<100; i++) data[i]=0;
const prompt = require('prompt-sync')();
const size = prompt('請輸入陣列大小(100以下)：');
inputarr (data, size);
process.stdout.write('您輸入的原始資料是：');
showdata(data, size);
quick(data, size, 0 ,size-1);
process.stdout.write('最終排序結果：');
showdata(data, size);

PHP                quick.php

mt_srand((double)microtime()*1000000);
$data =array();

if($_POST['submit'] !='送出') {
echo "
		<center>
     <form method='post' action='{$_SERVER['[PHP_SELF]']}'>
     請輸入陣列大小
     <input name='choice_size' type='text'>
		 <input type='submit' name='submit' value='送出''>
     </form>
    </center>
";
}
else{
	$choice_size=$_POST['choice_size'];
	echo "您輸入的數字：".$choice_size."<br>";
  
	for ($i=0; $i<$choice_size; $i++) {
  		$randval=mt_rand(1,500);
  		//echo $input_num."<br>";
  		//$data[]=$input_num;
  	  if (in_array($randval, $data)) { 
  	  //如果已產生過迴圈重跑
					$i--;
			}else{
			$data[] = $randval; 
			//若無重復則 將亂數塞入陣列
			}
  }
  echo "所選出的數列：<br>";
  print_arr($data);
  echo "--------------------------------------------<br>";

 	quick($data, $choice_size, 0, $choice_size-1);
  echo "--------------------------------------------<br>";
  echo "排列後的數列：<br>";
  //print_arr($sort_data);
  
}

function quick ($d, $size, $lf, $rg) {
	//第一筆鍵值為$d[$lf]
	if ($lf < $rg) {
		//排序資料的左邊與右邊
		$lf_idx=$lf+1;
		while ($d[$lf_idx] < $d[$lf]) {
			if ($lf_idx+1 > $size) break;
			$lf_idx +=1;
		}
		$rg_idx=$rg;
		while ($d[$rg_idx] > $d[$lf]) $rg_idx -=1;
		while ($lf_idx < $rg_idx) {
			$tmp=$d[$lf_idx];
			$d[$lf_idx]=$d[$rg_idx];
			$d[$rg_idx]=$tmp;
			$lf_idx +=1;
			while ($d[$lf_idx] < $d[$lf]) $lf_idx +=1;
			$rg_idx -=1;
			while ($d[$rg_idx] > $d[$lf]) $rg_idx -=1;
		}
		$tmp=$d[$lf];
		$d[$lf]=$d[$rg_idx];
		$d[$rg_idx]=$tmp;
		
		echo "排序中{$k}：";
		print_arr($d);
		quick($d, $size, $lf, $rg_idx-1);
		//以rg_idx為基準點分成左右兩半以遞迴方式
		quick($d, $size, $rg_idx+1, $rg);
		//分別為左右兩半進行排序直至完成排序
	}
	//return $d;
}


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

後記：目前(20250604)不知道程式哪裡出了問題？排序都有問題。 quick.php