PHP直接插入排序案例分析

這次帶給大家PHP直接插入排序案例分析，PHP直接插入排序的注意事項有哪些，下面就是實戰案例，一起來看一下。

演算法引入：

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

我們來看看這個順序：

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

#基本思想：

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

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

直接插入排序是由兩層的巢狀循環組成。外層循環標識並決定待比較的數值。內層循環為待比較數值決定其最終位置。直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續循環比較，直到找到比待比較數值小的並將待比較數值置入其後一位置，結束該次循環。

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

演算法實作：

<?php
//直接插入排序
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
function InsertSort(array &$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)
}

直接插入排序演算法的時間複雜度為

O(n^2)

。

直接插入排序是穩定排序。

相信看了本文案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！

推薦閱讀：

PHP快速排序演算法使用步驟詳解

#PHP產生推廣海報步驟詳解

以上是PHP直接插入排序案例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！