插入排序基本思路：將數(shù)組分為兩個(gè)區(qū)(已排序區(qū)和未排序區(qū))，假定數(shù)組的第一個(gè)元素處于已排序區(qū)， 第一個(gè)元素之后的所有元素都處于未排序部分。排序時(shí)用到雙層循環(huán)，外層循環(huán)用于從未排序部分中取出待排序元素，并逐步縮小未排序部分，內(nèi)層循環(huán)用于從已排序部分尋找插入位置（即不斷地從已排序部分尋找比待排序元素大的元素）， 然后將較大的已排序區(qū)的元素后移，后移的最終結(jié)果是已排序區(qū)元素的最后一個(gè)元素占據(jù)待排序元素原來的位置，而已排序區(qū)中間空出一個(gè)位置），最后將待排序元素插入元素后移之后留下的空位。
//插入排序
function insert_sort($arr) {
//獲取數(shù)組單元個(gè)數(shù)
$count = count($arr);
//外層循環(huán)用于從未排序區(qū)域中取出待排序元素
for ($i=1; $i < $count; $i++) {
//獲取當(dāng)前需要插入已排序區(qū)域的元素值
$temp = $arr[$i];
//內(nèi)層循環(huán)用于從已排序區(qū)域?qū)ふ掖判蛟氐牟迦胛恢?for ($j=$i-1; $j >= 0; $j--) {
//如果$arr[$i]比已排序區(qū)域的$arr[$j]小，就后移$arr[$j]
if ($temp < $arr[$j]) {
$arr[$j+1] = $arr[$j];
$arr[$j] = $temp;
} else {
//如果$arr[$i]不小于$arr[$j]，則對(duì)已排序區(qū)無需再排序
break;
}
}
}
return $arr;
}
$arr = array(6, 19, 26, 62, 88, 99, 18, 16, 1);
var_dump(insert_sort($arr));
測(cè)試結(jié)果：