日期：2025 年 6 月 4 日

7-8基數排序法

基數排序法和我們之前所討論到的排序法不一樣，它並不需要進行元素間的比較動作，而是屬於一種分配模式排序方式。基數排序法依照比較的方式。基數排序法依照比較的方向可分為最有效鍵優先(Most Significant Digit First, MSD)和最無效鍵優先(Least Significaant Digit First, LSD)兩種。MSD法是從最左邊的位數開始比較，而LSD則是從最右邊的位數開始比較。

以下的範例我們以LSD將三位數的整數資料來加以排序，它是依個位數、十位數、百位數來進行排序。請直接看以下最無效鍵優先(LSD)例子的說明，便可清楚的知道它的動作原理：

原始資料如下：

JS            radix.js

//基數排序法 由小到大排序
var inputarr=(data, size)=> {
	for (i=0; i<size; i++) {
		data[i]=Math.floor(Math.random()*1000);
		//設定data值最大為3位數
	}
}

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

var radix=(data, size)=> {
	for (n=1; n<=100; n=n*10)
	{
		var tmp=new Array();
		for (var i=0; i<10; i++) {
			tmp[i]=new Array();
			for (var j=0; j<10; j++) {
				tmp[i][j]=0;
			}
		}

		for (i=0; i<size; i++) 
		{
			m=Math.floor((data[i]/n))%10;
			tmp[m][i]=data[i];
		}
		k=0;
		for (i=0; i<10; i++)
		{
			for(j=0; j<10; j++)
			{
				if (tmp[i][j] !=0)
				{
					data[k]=tmp[i][j];
					k++;
				}
			}
		}
		process.stdout.write("經過"+n+"位數排序後：");
		showdata(data, size);
	}

}

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