本意是想研究一下希爾排序的,因為希爾排序和快速排序沒有爭議的是排序最快的兩種算法,但無奈希爾排序是以插入排序為基礎的,所以只得先研究一下插入排序.

?

插入排序基本思想:

?

插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的數據序列的適當位置，直到全部記錄插入完成為止。

假設待排序的記錄存放在數組R[0…n-1]中。初始時，R[0]自成1個有序區，無序區為R[1…n-1]。從i=1起直至i= n-1為止，依次將R[i]插入當前的有序區R[0…i-1]中，生成含n個記錄的有序區。通常將一個記錄R[i](i=1，2，…，n-1)插入到當前的有序區，使得插入后仍保證該區間里的記錄是按關鍵字有序的操作稱第i趟插入排序。排序過程的某一中間時刻，R被劃分成兩個子區間R[0…i-1]（已排好序的有序區）和[i…n-1]（當前未排序的部分，可稱無序區）。插入排序的基本操作是將當前無序區的第1個記錄R[0]插人到有序區R[0…i-1]中適當的位置上，使 R[0…i]變為新的有序區。因為這種方法每次使有序區增加1個記錄，通常稱增量法。
?

?

排序示意圖：

?

?

?

代碼實現 :

?

//插入排序
function insertSort($arr)
{$count = count($arr);for ($i = 1; $i < $count; $i++){$temp = $arr[$i];//設置哨兵for ($j = $i-1; $j >= 0; $j--){if($arr[$j] > $temp){$arr[$j+1] = $arr[$j];$arr[$j] = $temp;}}} return $arr;
}$arr = array(70,30,40,10,80,20,90,100,75,60,45);
var_dump(insertSort($arr));

?

結果:

array (size=11)0 =>  101 =>  202 =>  303 =>  404 =>  455 =>  606 =>  707 =>  758 =>  809 =>  9010 =>  100 (size=11)0 =>  101 =>  202 =>  303 =>  404 =>  455 =>  606 =>  707 =>  758 =>  809 =>  9010 =>  100

?

?

?