鏈表插入排序（插入排序思路）

關(guān)于鏈表插入排序，插入排序思路這個(gè)問題很多朋友還不知道，今天小六來為大家解答以上的問題，現(xiàn)在讓我們一起來看看吧！

1、轉(zhuǎn)個(gè)過來插入排序(Insertion Sort)的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。

2、???? 　本節(jié)介紹兩種插入排序方法：直接插入排序和希爾排序。

3、 直接插入排序基本思想基本思想???? 　假設(shè)待排序的記錄存放在數(shù)組R[1..n]中。

4、初始時(shí)，R[1]自成1個(gè)有序區(qū)，無序區(qū)為R[2..n]。

5、從i=2起直至i=n為止，依次將R[i]插入當(dāng)前的有序區(qū)R[1..i-1]中，生成含n個(gè)記錄的有序區(qū)。

6、2、第i-1趟直接插入排序：???? 　通常將一個(gè)記錄R[i](i=2，3，…，n-1)插入到當(dāng)前的有序區(qū)，使得插入后仍保證該區(qū)間里的記錄是按關(guān)鍵字有序的操作稱第i-1趟直接插入排序。

7、???? 　排序過程的某一中間時(shí)刻，R被劃分成兩個(gè)子區(qū)間R[1．．i-1]（已排好序的有序區(qū)）和R[i．．n]（當(dāng)前未排序的部分，可稱無序區(qū)）。

8、???? 　直接插入排序的基本操作是將當(dāng)前無序區(qū)的第1個(gè)記錄R[i]插人到有序區(qū)R[1．．i-1]中適當(dāng)?shù)奈恢蒙?，使R[1．．i]變?yōu)樾碌挠行騾^(qū)。

9、因?yàn)檫@種方法每次使有序區(qū)增加1個(gè)記錄，通常稱增量法。

10、???? 　插入排序與打撲克時(shí)整理手上的牌非常類似。

11、摸來的第1張牌無須整理，此后每次從桌上的牌(無序區(qū))中摸最上面的1張并插入左手的牌(有序區(qū))中正確的位置上。

12、為了找到這個(gè)正確的位置，須自左向右(或自右向左)將摸來的牌與左手中已有的牌逐一比較。

13、一趟直接插入排序方法1．簡單方法???? 　首先在當(dāng)前有序區(qū)R[1..i-1]中查找R[i]的正確插入位置k(1≤k≤i-1)；然后將R[k．．i-1]中的記錄均后移一個(gè)位置，騰出k位置上的空間插入R[i]。

14、??注意：???? 　若R[i]的關(guān)鍵字大于等于R[1．．i-1]中所有記錄的關(guān)鍵字，則R[i]就是插入原位置。

15、2．改進(jìn)的方法　　一種查找比較操作和記錄移動操作交替地進(jìn)行的方法。

16、具體做法：???? 　將待插入記錄R[i]的關(guān)鍵字從右向左依次與有序區(qū)中記錄R[j](j=i-1，i-2，…，1)的關(guān)鍵字進(jìn)行比較：???? ?、?若R[j]的關(guān)鍵字大于R[i]的關(guān)鍵字，則將R[j]后移一個(gè)位置；?????? ②若R[j]的關(guān)鍵字小于或等于R[i]的關(guān)鍵字，則查找過程結(jié)束，j+1即為R[i]的插入位置。

17、???? 　關(guān)鍵字比R[i]的關(guān)鍵字大的記錄均已后移，所以j+1的位置已經(jīng)騰空，只要將R[i]直接插入此位置即可完成一趟直接插入排序。

18、直接插入排序算法1．算法描述?? void lnsertSort(SeqList R)??? { //對順序表R中的記錄R[1..n]按遞增序進(jìn)行插入排序???? int i，j；???? for(i=2;i<=n；i++) //依次插入R[2]，…，R[n]?????? if(R[i].key

19、??? 　 哨兵有兩個(gè)作用：　?、?進(jìn)人查找(插入位置)循環(huán)之前，它保存了R[i]的副本，使不致于因記錄后移而丟失R[i]的內(nèi)容；　?、?它的主要作用是：在查找循環(huán)中"監(jiān)視"下標(biāo)變量j是否越界。

20、一旦越界(即j=0)，因?yàn)镽[0].key和自己比較，循環(huán)判定條件不成立使得查找循環(huán)結(jié)束，從而避免了在該循環(huán)內(nèi)的每一次均要檢測j是否越界(即省略了循環(huán)判定條件"j>=1")。

21、??注意：　?? ① 實(shí)際上，一切為簡化邊界條件而引入的附加結(jié)點(diǎn)(元素)均可稱為哨兵。

22、　　?? 【例】單鏈表中的頭結(jié)點(diǎn)實(shí)際上是一個(gè)哨兵　　② 引入哨兵后使得測試查找循環(huán)條件的時(shí)間大約減少了一半，所以對于記錄數(shù)較大的文件節(jié)約的時(shí)間就相當(dāng)可觀。

23、對于類似于排序這樣使用頻率非常高的算法，要盡可能地減少其運(yùn)行時(shí)間。

24、所以不能把上述算法中的哨兵視為雕蟲小技，而應(yīng)該深刻理解并掌握這種技巧。

25、給定輸入實(shí)例的排序過程???? 　設(shè)待排序的文件有8個(gè)記錄，其關(guān)鍵字分別為：49，38，65，97，76，13，27，49。

26、為了區(qū)別兩個(gè)相同的關(guān)鍵字49，后一個(gè)49的下方加了一下劃線以示區(qū)別。

27、其排序過程見【動畫模擬演示】算法分析1．算法的時(shí)間性能分析 ???? 　對于具有n個(gè)記錄的文件，要進(jìn)行n-1趟排序。

28、???? 各種狀態(tài)下的時(shí)間復(fù)雜度：┌─────────┬─────┬──────┬──────┐│ 初始文件狀態(tài)????? │??? 正序??? │????? 反序??? │無序(平均)?? │├─────────┼─────┼──────┼──────┤│ 第i趟的關(guān)鍵?????? │??? 1?????? │????? i+1???? │ （i-2）/2?? ││ 字比較次數(shù)??????? │?????????? │???????????? │???????????? │├─────────┼─────┼──────┼──────┤│總關(guān)鍵字比較次數(shù)?? │??? n-1???? │(n+2)(n-1)/2│ ≈n2/4????? │├─────────┼─────┼──────┼──────┤│第i趟記錄移動次數(shù) │??? 0?????? │ i+2???????? │ （i-2）/2?? │├─────────┼─────┼──────┼──────┤│總的記錄移動次數(shù)?? │??? 0?????? │(n-1)(n+4)/2│ ≈n2/4????? │├─────────┼─────┼──────┼──────┤│時(shí)間復(fù)雜度???????? │?? 0（n）?? │ O（n2）???? │ O（n2）???? │└─────────┴─────┴──────┴──────┘注意：???? 　初始文件按關(guān)鍵字遞增有序，簡稱"正序"。

29、　???? 初始文件按關(guān)鍵字遞減有序，簡稱"反序"。

30、 2．算法的空間復(fù)雜度分析???? 　算法所需的輔助空間是一個(gè)監(jiān)視哨，輔助空間復(fù)雜度S(n)=O(1)。

31、是一個(gè)就地排序。

32、3．直接插入排序的穩(wěn)定性???? 　直接插入排序是穩(wěn)定的排序方法。

本文分享完畢，希望對大家有所幫助。

標(biāo)簽：