排序演算法篇--之直接插入排序

　　直接插入排序是將一個記錄插入到已經排好序的有序表中，從而得到一個新的記錄數加1的有序表。

　　下麵的代碼中會先假設數組的第一個元素是已經拍好序的有序表，然後從第二個元素開始遍歷剩下的元素。

　　所以呢，第一個for迴圈是遍歷待插入的元素，第二個for迴圈是遍歷被插入的有序表，並將待插入元素與有序表的元素比較，將待插入元素插在合適位置。

 1 <?php
 2     $arr = array(9,8,7,6,5,0,3,2,1,4);
 3 
 4     /**
 5      * 返回通過插入排序演算法重新排序後的數組
 6      * @param $array array 要進行排序的數組
 7      * return array 返回排序後的數組
 8      */
 9     function InsertSort($array){
10         
11         for($i=1;$i<count($array);$i++){ //，假設第一個數已經排序好的，從第二個數開始迴圈
12             if($array[$i]<$array[$i-1]){    //當前數比他前面的一個數小
13 
14                 $temp = $array[$i];
15                 for($j = $i-1;$j >= 0 && $array[$j] > $temp;$j--){//遍歷當前元素前面的元素，若比當前的數大則記錄後移
16                 
17                     $array[$j+1] = $array[$j];//記錄後移
18                 }
19                 $array[$j+1] = $temp;    
20             }
21         }
22 
23         return $array;
24     }
25 
26     $result = InsertSort($arr);
27     echo '<pre>';
28     print_r($result);