PHP排序：php插入排序的算法思想及算法實現(xiàn)

2020-03-22 17:38:51

字體：大中小

來源：轉載

供稿：網友

本篇文章給大家?guī)淼膬热菔顷P于PHP排序：php插入排序的算法思想及算法實現(xiàn)，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

算法引入：

在這里我們依然使用《大話數據結構》里面的一個例子：

撲克牌是我們幾乎每個人都玩過的游戲。平時我們開始的時候一般都是一個人發(fā)牌，其他人都是一邊摸牌，一邊理牌，假如你摸上的第一張牌是 5，第二張牌是 3，自然而然的我們把 3 插到 5 的前面；第三張牌是 4，查到 3 和 5 的中間；第四張牌是 6，放到 5 的后面；第五張牌是 2，插到 3 的前面；……。最后當我們摸完所有的牌時，手上的牌都是從小到大（點數）排好序的。

我們來看這個順序：

5 3 // 將 3 插入只有一個元素 5 的有序表中
3 5 4 // 將 4 插入有兩個元素 3 5 的有序表中
3 4 5 6 // 將 6 插入有兩個元素 3 4 5 的有序表中
3 4 5 6 2 // 將 2 插入有兩個元素 3 4 5 6 的有序表中
2 3 4 5 6

直接插入排序的基本思想是：每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。

第一趟比較前兩個數，然后把第二個數按大小插入到有序表中；第二趟把第三個數據與前兩個數從后向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。

直接插入排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標識并決定待比較的數值。內層循環(huán)為待比較數值確定其最終位置。直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環(huán)是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數值小的并將待比較數值置入其后一位置，結束該次循環(huán)。

插入排序的基本方法是：每步將一個待排序的記錄按其關鍵字的大小插到前面已經排序的序列中的適當位置，直到全部記錄插入完畢為止。

插入排序算法實現(xiàn)：

// 直接插入排序function swap( $arr,$a,$b)$temp = $arr[$a];$arr[$a] = $arr[$b];$arr[$b] = $temp;function insertSort( $arr)$count = count($arr);for ($i=1; $i $count; $i++) {  $temp = $arr[$i]; for ($j=$i-1; $j = 0 $arr[$j] $temp;$j--) {  $arr[$j + 1] = $arr[$j]; //記錄后移 $arr[$j + 1] = $temp; //插入到正確的位置$arr = array(9,1,5,8,3,7,4,6,2);insertSort($arr);var_dump($arr);

運行結果：
array(9) {
[0]=
int(1)
[1]=
int(2)
[2]=
int(3)
[3]=
int(4)
[4]=
int(5)
[5]=
int(6)
[6]=
int(7)
[7]=
int(8)
[8]=
int(9)
}