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>";
}
