PHP排序算法之插入排序

rose 發布于2019-07-01 10:30 / 1853人閱讀

摘要：直接插入排序是由兩層嵌套循環組成的。插入排序的基本方法是每步將一個待排序的記錄按其關鍵字的大小插到前面已經排序的序列中的適當位置，直到全部記錄插入完畢為止。算法實現直接插入排序記錄后移插入到正確的位置運行結果

算法引入：

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

撲克牌是我們幾乎每個人都玩過的游戲。平時我們開始的時候一般都是一個人發牌，其他人都是一邊摸牌，一邊理牌，假如你摸上的第一張牌是 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)趟掃描以后就完成了整個排序過程。

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

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

算法實現：
// 直接插入排序
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)
}

云服務器 GPU云服務器插入排序算法 java插入排序算法用php實現插入排序插入排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/29225.html

PHP算法之四大基礎算法

摘要：而在證明算法是正確的基礎上，第二步就是分析算法的時間復雜度。算法的時間復雜度反映了程序執行時間隨輸入規模增長而增長的量級，在很大程度上能很好反映出算法的優劣與否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言雖然工作中，你覺得自己并沒有涉及到算法這方面的東西，但是算法是程序的...

isLishude 2019-07-01 12:31 評論0 收藏0
PHP面試之四：邏輯與算法

摘要：數據結構常見數據結構數組是最簡單而且應用最廣泛的數據結構特征使用連續內存空間來存儲存放相同類型或著衍生類型的元素數組比較特別，可以存放八種數據類型通過下標來訪問集合特征保存不重復的元素字典特征就是關聯數組，以形式存儲棧，與隊列相似特征存儲數數據結構常見數據結構 Array 數組是最簡單而且應用最廣泛的數據結構特征： 1、使用連續內存空間來存儲 2、存放相同類型或著衍生類型...

smartlion 2019-06-28 14:11 評論0 收藏0
PHP 算法02之插入排序

摘要：最后看第三位和第四位，發現左邊小于右邊，無需交換，最終是，，，。總結一下就是從左到右依次選中一個數和左邊比較，這個數小于左邊就交換，交換完在和左邊比較，直到交換到比左邊大了之后，換下一個數，最后數字依次處理后，數據即從小到大排序。描述舉例4個數: 7,4,3,8 從左往右兩兩比較,即 7和4比較，發現7大于4，那么交換，數列變成 4,7,3,8 。然后我們再看第2位和第三位，發...

awesome23 2019-07-01 10:20 評論0 收藏0
PHP基礎算法之插入排序法

摘要：插入排序法獲得當前需要比較的元素值。將這個元素插入到已經排序好的序列內。

stormzhang 2019-06-27 15:57 評論0 收藏0