資訊專欄INFORMATION COLUMN
摘要：插入排序插入排序英語(yǔ)是一種簡(jiǎn)單直觀的排序算法。插入排序在實(shí)現(xiàn)上，通常采用排序即只需用到的額外空間的排序，因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。一般來(lái)說(shuō)，插入排序都采用在數(shù)組上實(shí)現(xiàn)。
導(dǎo)語(yǔ)
關(guān)于排序的算法，就此告一段落。冒泡排序、快速排序、選擇排序、加上本篇的插入排序，這四種算法都是相對(duì)簡(jiǎn)單，容易理解的。更復(fù)雜的算法，就不獻(xiàn)丑了，以免誤人子弟。
插入排序插入排序（英語(yǔ)：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到 O(1) 的額外空間的排序），因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素，將該元素移到下一位置
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟2~5
來(lái)自維基百科的介紹。重點(diǎn)在于步驟 2~5。
動(dòng)圖演示 實(shí)例= 0; $k--) {
// 條件成立，比較值后挪一位，將當(dāng)前值替換成比較值
// 倒序 $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排序算法系列：插入排序。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/30040.html
摘要：直接插入排序是由兩層嵌套循環(huán)組成的。插入排序的基本方法是每步將一個(gè)待排序的記錄按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當(dāng)位置，直到全部記錄插入完畢為止。算法實(shí)現(xiàn)直接插入排序記錄后移插入到正確的位置運(yùn)行結(jié)果 算法引入： 在這里我們依然使用《大話數(shù)據(jù)結(jié)構(gòu)》里面的一個(gè)例子： 撲克牌是我們幾乎每個(gè)人都玩過(guò)的游戲。平時(shí)我們開(kāi)始的時(shí)候一般都是一個(gè)人發(fā)牌，其他人都是一邊摸牌，一邊理牌，假如你摸上...
摘要：一個(gè)常見(jiàn)的例子就是優(yōu)先隊(duì)列，還有排序算法之一的堆排序。另外我們還將學(xué)習(xí)堆排序，并將使用實(shí)現(xiàn)堆。堆排序在堆排序中，我們需要用給定的值構(gòu)建一個(gè)一個(gè)堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構(gòu)建一個(gè)堆。 堆是什么？ 堆是基于樹(shù)抽象數(shù)據(jù)類型的一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于許多算法和數(shù)據(jù)結(jié)構(gòu)中。一個(gè)常見(jiàn)的例子就是優(yōu)先隊(duì)列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...
摘要：而在證明算法是正確的基礎(chǔ)上，第二步就是分析算法的時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)，在很大程度上能很好反映出算法的優(yōu)劣與否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言 雖然工作中，你覺(jué)得自己并沒(méi)有涉及到算法這方面的東西，但是算法是程序的...
摘要：它的基本思想是通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 選擇排序 選擇排序主要是將假設(shè)數(shù)組中的第一個(gè)是最小的，循環(huán)與數(shù)組中的第一個(gè)進(jìn)行比較 如果比其還小 則記錄下標(biāo) 進(jìn)行數(shù)值交換 效率相對(duì)冒泡來(lái)說(shuō)比較高 function s...
摘要：的陣列視為基本型別，所以必須用傳參考才能修改原陣列插入排序快速排序歸并排序堆排序獲取個(gè)數(shù)處理一半的數(shù)據(jù) function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列 for ($i = 0; $i < count($arr) - 1; $i++) for ($j = 0; $j < count($arr)...
閱讀 3855·2021-09-29 09:34
閱讀 3786·2021-09-27 13:34
閱讀 580·2021-09-24 09:47
閱讀 3045·2019-08-30 15:53
閱讀 1821·2019-08-26 13:54
閱讀 2096·2019-08-26 13:43
閱讀 545·2019-08-23 14:47
閱讀 1752·2019-08-23 14:28
