直接插入排序（Straight Insertion Sorting）的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重復n-1次可完成排序過程。
把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具體實施過程為:先把a[i]賦值給變量t,然後將t依次與a[i-1],a[i-2],...進行比較,將比t大的元素右移一個位置,直到發現某個j(0<=j<=i-1),使得a[j]<=t或j為(-1),把t賦值給a[j+1].
改進的方法
一種查找比較操作和記錄移動操作交替地進行的方法。
具體做法：
將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=i-1，i-2，…，1)的關鍵字進行比較：
① 若R[j]的關鍵字大於R[i]的關鍵字，則將R[j]後移一個位置；
②若R[j]的關鍵字小於或等於R[i]的關鍵字，則查找過程結束，j+1即為R[i]的插入位置。
關鍵字比R[i]的關鍵字大的記錄均已後移，所以j+1的位置已經騰空，只要將R[i]直接插入此位置即可完成一趟直接插入排序。
即是從新的序列的後面開始比較，並且進行移位；
php代碼：
[php]
<?php
echo '<pre>';
$arr = array(90,5,3,9,2,6,10,30,0,0,0,0,0);
print_r(insertSort($arr));
function insertSort($arr){
$res = array();//要插入的空間
$res[0] = $arr[0];//先把第一個字符放進來
for($i=1;$i<count($arr);$i++){//循環從第二個字符開始，第一個已經放入$res裡面了
$c = count($res);//計算循環次數
for($j=$c;$j>=0;$j--){
if($res[$j-1]<=$arr[$i]){//$j-1是要比較的值，$j是空出來即將進行插入的位
$res[$j] = $arr[$i];
break;//已經把值插入，結束這個值的for循環
}else{
$res[$j] = $res[$j-1];//進行向後移位
}
}
}
return $res;
}
?>
作者：dats0407
