尤瑟納而女士借阿德里安之口云静檬，當(dāng)一個人寫作或計算時帘营，就超越了性別图谷，甚至超越了人類——當(dāng)你寫作和計算時翩活，就是在思考阱洪。
聊聊<<大話>>中直接插入排序的那些坑
我就不說為什么要學(xué)習(xí)直接插入排序,那樣豈不是太老套了.今天我就說說看<<大話數(shù)據(jù)結(jié)構(gòu)>>中的直接插入排序算法的坑,一開始看大話數(shù)據(jù)結(jié)構(gòu)的時候,就曾經(jīng)有很多人跟我說,這本書有很多的坑,別跳進(jìn)去,今天我就義無反顧的跳了進(jìn)去.而且是不帶回頭的??.整整四頁紙的直接插入排序算法,我搞了一天(可能是我太笨了)!一開始我在Xcode(Mac上OC語言的編譯器)上按照OC的方式把大話數(shù)據(jù)結(jié)構(gòu)的代碼擼了一遍.還沒編譯運行呢,我就看出一個問題來,數(shù)組越界....我的內(nèi)心是崩潰的.但是我稍稍的修改了一下.一運行,還是不對,沒辦法,我只好從網(wǎng)上找各種關(guān)于直接插入排序算法的技巧.然后,我就發(fā)現(xiàn)問題的原因是哨兵的問題,好了,我原諒他了..因為函數(shù)不同,所以,我只好重新用在本子上演算過程.里里外外花了一下午左右吧.下面我就把不同的位置標(biāo)記出來,為后來之人指一條明路.不說了美圖我會這么說?直接上圖!
這個錯誤是導(dǎo)致數(shù)組越界.
哨兵問題
直接插入排序算法概念及基本思想
直接插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置菠镇，直到全部記錄插入完成為止冗荸。
直接插入排序算法的實現(xiàn)
首先我們看一下,用文字是如何表達(dá)實現(xiàn)過程.
設(shè)數(shù)組為dataArray[0…n-1]。
1. 初始時利耍，dataArray[0]自成1個有序區(qū)蚌本，無序區(qū)為dataArray[1..n-1]。令i=1
2. 將dataArray[i]并入當(dāng)前的有序區(qū)dataArray[0…i-1]中形成a[0…i]的有序區(qū)間隘梨。
3. i++并重復(fù)第二步直到i==n-1程癌。排序完成。
文字說的還是有點生硬,看一下用OC語言代碼是如何實現(xiàn)直接插入排序算法的.代碼的注釋已經(jīng)很詳細(xì),需要加斷點自己查看控制臺的打印信息.這里我寫在了ViewController的ViewDidLoad中.
- (void)viewDidLoad {
[super viewDidLoad];
//數(shù)據(jù)源數(shù)組
NSMutableArray *dataArray = [NSMutableArray arrayWithArray:@[@0,@5,@3,@4,@6,@2]];
int i,j;
NSNumber *temp = [[NSNumber alloc]init];//這里就是要修改過的哨兵(OC版本的,其他語言自行探索??)
for (i = 1; i< dataArray.count; i++) {
NSLog(@"%@",dataArray);//打印每一次的變化,不管是否有新的元素插入有序表中(需要斷點打印查看)
//判斷當(dāng)前的下標(biāo)i的數(shù)組元素是否大于下標(biāo)i-1的數(shù)組元素,如果大于,那么不做操作..反之~~~
if (dataArray[i]<dataArray[i-1]) {
temp = dataArray[i];
//找到合適位置,插入有序表中
for (j = i-1 ; dataArray[j] > temp; j--) {
dataArray[j+1] = dataArray[j];
NSLog(@"%@",dataArray);//打印每一次元素移動之后,數(shù)組的變化情況(需要斷點查看)
}
dataArray[j+1] = temp;
NSLog(@"%@",dataArray);//打印每一次元素插入有序表中之后數(shù)組的變化(需要斷點打印)
}
}
NSLog(@"%@",dataArray);//排序完成打印數(shù)組(需要斷點查看)
}
直接插入排序算法代碼過程部分講解
第一次遍歷( i = 1 , j= 0,temp = nil )
- 第一步,判斷dataArray[1]和dataArray[0],因為5> 0,所以不走if里面的所以條件,也就是可以這么說,現(xiàn)在5已經(jīng)插入了有序表中,有序表為{0,5}(假裝有圖片,不對,是假裝有有序表...);現(xiàn)在的數(shù)組沒有發(fā)生改變,為{0,5,3,4,6,2};跳出第一遍循環(huán).
第二次遍歷( i = 2 , j= 0,temp = nil )
第一步,判斷dataArray[2]和dataArray[1],因為3< 5,所以走if里面的所有代碼.
-
第二步,if里面的代碼,首先把dataArray[2]賦值給temp,所以temp = 3;接下來就是for循環(huán)插到有序表表{0,5}中,j = 1,for循環(huán)的條件dataArray[j] > temp,即為5> 3,條件成立. dataArray[3] = dataArray[2] = 5 ; 接著j-- , j = 0, 判斷for循環(huán)的條件dataArray[j] > temp,即為0> 3,條件不成立.跳出循環(huán).dataArray[j+1] = dataArray[1] = 3,這次的插入操作就完成了.插入操作完成的數(shù)組為{0,3,5,4,6,2};控制打印如下.
數(shù)組元素3完成插入操作之后的打印信息
往后的數(shù)組元素4以及數(shù)組元素2都需要做插入移動操作,數(shù)組元素6不需要做操作,往后的步驟和上面的步驟類似.我就不做一一詳細(xì)的講解了.
各位看官,在查看上面的代碼之前 , 你需要做的一件事情,那就是準(zhǔn)備好一張紙??和一支筆??,來記錄每一次的變化.這樣才能更好的了解直接插入排序算法的全過程.就如同這樣....(書寫請無視,謝謝??..)
最后附上OC版的Demo,各位看官自行斷點查看,如果有任何疑問請在評論去回復(fù),謝謝.
