資訊專欄INFORMATION COLUMN
摘要：直接插入排序是由兩層嵌套循環(huán)組成的。插入排序的基本方法是每步將一個(gè)待排序的記錄按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當(dāng)位置，直到全部記錄插入完畢為止。算法實(shí)現(xiàn)直接插入排序記錄后移插入到正確的位置運(yùn)行結(jié)果
算法引入：
在這里我們依然使用《大話數(shù)據(jù)結(jié)構(gòu)》里面的一個(gè)例子：
撲克牌是我們幾乎每個(gè)人都玩過的游戲。平時(shí)我們開始的時(shí)候一般都是一個(gè)人發(fā)牌，其他人都是一邊摸牌，一邊理牌，假如你摸上的第一張牌是 5，第二張牌是 3，自然而然的我們把 3 插到 5 的前面；第三張牌是 4，查到 3 和 5 的中間；第四張牌是 6，放到 5 的后面；第五張牌是 2，插到 3 的前面；……。最后當(dāng)我們摸完所有的牌時(shí)，手上的牌都是從小到大（點(diǎn)數(shù)）排好序的。
我們來看這個(gè)順序：
5 3 // 將 3 插入只有一個(gè)元素 5 的有序表中
3 5 4 // 將 4 插入有兩個(gè)元素 3 5 的有序表中
3 4 5 6 // 將 6 插入有兩個(gè)元素 3 4 5 的有序表中
3 4 5 6 2 // 將 2 插入有兩個(gè)元素 3 4 5 6 的有序表中
2 3 4 5 6
直接插入排序的基本思想是 ： 每次從無序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。
第一趟比較前兩個(gè)數(shù)，然后把第二個(gè)數(shù)按大小插入到有序表中； 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描，把第三個(gè)數(shù)按大小插入到有序表中；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過程。
直接插入排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標(biāo)識(shí)并決定待比較的數(shù)值。內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置。直接插入排序是將待比較的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，所以外層循環(huán)是從第二個(gè)數(shù)值開始的。當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。
插入排序的基本方法是：每步將一個(gè)待排序的記錄按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當(dāng)位置，直到全部記錄插入完畢為止。
算法實(shí)現(xiàn)：
// 直接插入排序
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);
運(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)
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/29225.html
摘要：而在證明算法是正確的基礎(chǔ)上，第二步就是分析算法的時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長而增長的量級(jí)，在很大程度上能很好反映出算法的優(yōu)劣與否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言 雖然工作中，你覺得自己并沒有涉及到算法這方面的東西，但是算法是程序的...
摘要：數(shù)據(jù)結(jié)構(gòu)常見數(shù)據(jù)結(jié)構(gòu)數(shù)組是最簡單而且應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)特征使用連續(xù)內(nèi)存空間來存儲(chǔ)存放相同類型或著衍生類型的元素?cái)?shù)組比較特別，可以存放八種數(shù)據(jù)類型通過下標(biāo)來訪問集合特征保存不重復(fù)的元素字典特征就是關(guān)聯(lián)數(shù)組，以形式存儲(chǔ)棧，與隊(duì)列相似特征存儲(chǔ)數(shù) 數(shù)據(jù)結(jié)構(gòu) 常見數(shù)據(jù)結(jié)構(gòu) Array 數(shù)組是 最簡單 而且 應(yīng)用最廣泛 的數(shù)據(jù)結(jié)構(gòu) 特征： 1、使用連續(xù)內(nèi)存空間來存儲(chǔ) 2、存放相同類型或著衍生類型...
摘要：最后看第三位和第四位，發(fā)現(xiàn)左邊小于右邊，無需交換，最終是，，，?？偨Y(jié)一下就是從左到右依次選中一個(gè)數(shù)和左邊比較，這個(gè)數(shù)小于左邊就交換，交換完在和左邊比較，直到交換到比左邊大了之后，換下一個(gè)數(shù)，最后數(shù)字依次處理后，數(shù)據(jù)即從小到大排序。 描述 舉例4個(gè)數(shù): 7,4,3,8 從左往右兩兩比較,即 7和4比較，發(fā)現(xiàn)7大于4，那么交換，數(shù)列變成 4,7,3,8 。 然后我們?cè)倏吹?位和第三位，發(fā)...
閱讀 2212·2021-11-22 11:56
閱讀 2654·2021-10-08 10:05
閱讀 7836·2021-09-22 15:53
閱讀 1925·2021-09-22 15:29
閱讀 2245·2021-09-08 09:35
閱讀 3366·2021-09-07 10:12
閱讀 1388·2019-08-30 13:11
閱讀 1989·2019-08-28 17:54
