PHP排序算法之直接插入排序(Straight Insertion Sort)實(shí)例分析

本文實(shí)例講述了PHP排序算法之直接插入排序(Straight Insertion Sort)。分享給大家供大家參考，具體如下：

算法引入：

在這里我們依然使用《大話數(shù)據(jù)結(jié)構(gòu)》里面的一個例子：

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

我們來看這個順序：

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

基本思想：

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

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

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

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

算法實(shí)現(xiàn)：

?php
//直接插入排序
function swap(array $arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
function InsertSort(array $arr){
  $count = count($arr);
  //數(shù)組中第一個元素作為一個已經(jīng)存在的有序表
  for($i = 1;$i  $count;$i ++){
    $temp = $arr[$i];   //設(shè)置哨兵
    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);

運(yùn)行結(jié)果：

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)
}

直接插入排序算法的時間復(fù)雜度為 O(n^2)。

直接插入排序是穩(wěn)定排序。

本文參考自《大話數(shù)據(jù)結(jié)構(gòu)》，在此僅作記錄，方便以后查閱，大神勿噴！

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《php排序算法總結(jié)》、《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》

希望本文所述對大家PHP程序設(shè)計(jì)有所幫助。