PHP 實現插入排序
導語
關於排序的演算法,就此告一段落。氣泡排序、 快速排序 、選擇排序、加上本篇的插入排序,這四種演算法都是相對簡單,容易理解的。更復雜的演算法,就不獻醜了,以免誤人子弟。
插入排序
插入排序(英語:Insertion Sort)是一種簡單直觀的 排序演算法 。它的工作原理是通過構建有序序列,對於未排序資料,在已排序序列中從後向前掃描,找到相應位置並插入。 插入排序 在實現上,通常採用in-place排序(即只需用到 O(1) 的額外空間的排序),因而在從後向前掃描過程中,需要反覆把已排序元素逐步向後挪位,為最新元素提供插入空間。
一般來說, 插入排序 都採用in-place在陣列上實現。具體演算法描述如下:
- 從第一個元素開始,該元素可以認為已經被排序
- 取出下一個元素,在已經排序的元素序列中從後向前掃描
- 如果該元素(已排序)大於新元素,將該元素移到下一位置
- 重複步驟3,直到找到已排序的元素小於或者等於新元素的位置
- 將新元素插入到該位置後
- 重複步驟2~5
來自維基百科的介紹。重點在於步驟 2~5。
動圖演示
例項
<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16]; function insertSort($arr) { $count = count($arr); if ($count < 2) { return $arr; } for ($i = 1; $i < $count; $i++) { // 當前值 $temp = $arr[$i]; for ($k = $i - 1; $k >= 0; $k--) { // 條件成立,比較值後挪一位,將當前值替換成比較值 // 倒序 $temp > $arr[$k] if ($temp < $arr[$k]) { $arr[$k + 1] = $arr[$k]; $arr[$k] = $temp; } } } return $arr; } print_r(insertSort($arr)); // Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )
參考資料: 插入排序 、 PHP排序算法系列:插入排序 。