9.5.1?直接插入排序算法

??????? 撲克牌是我們幾乎每個人都可能從事過的游戲。而最基本的撲克玩法都是一邊摸牌，一邊理牌。假如我們拿到了這樣一手牌，如圖9-5-1。啊，似乎是同花順呀，別急，我們得理一理順序才知道是否是真的同花順。請問，如果是你，應該如何理牌呢？

?

? ??????? 應該說，哪怕你是第一次玩撲克牌，只要認識這些數字，理牌的方法都是不用教的。將3和4移動到5的左側，再將2移動到最左側，順序就算是理好了。這里，我們的理牌方法，就是直接插入排序法。
????????直接插入排序（Straight Insertion Sort）的基本操作是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增1的有序表。
??????? 顧名思義，從名稱上也可以知道它是一種插入排序的方法。我們來看直接插入排序法的代碼。（注：要了解算法的原理，直接看代碼和后面的解釋并不是最好的辦法。將代碼輸入到電腦中，運行并斷點逐行跟蹤，參照本文的講解和圖示，觀察變量的變化情況，才會收到比較好的效果。這里的代碼全是用C語言編寫，不過對于擅長C#的讀者應該不存在閱讀難度。）

void InsertSort(SqList *L) { int i,j;for(i=2;i<=L->length;i++){if (L->r[i]<L->r[i-1]) /* 需將L->r[i]插入有序子表 */{L->r[0]=L->r[i]; /* 設置哨兵 */for(j=i-1;L->r[j]>L->r[0];j--)L->r[j+1]=L->r[j]; /* 記錄后移 */L->r[j+1]=L->r[0]; /* 插入到正確位置 */}} }

1)?程序開始運行，此時我們傳入的SqList參數的值為length=6,r[6]={0,5,3,4,6,2}，其中r[0]=0將用于后面起到哨兵的作用。
2)?第4～13行就是排序的主循環。i從2開始的意思是我們我們假設r[1]=5已經放好位置，后面的牌其實就是插入到它的左側還是右側的問題。
3)?第6行，此時i=2，L.r[i]=3比L.r[i-1]=5要小，因此執行第8～11行的操作。第8行，我們將L.r[0]賦值為L.r[i]=3的目的是為了起到第9～10行的循環終止的判斷依據。如圖9-5-2。圖中下方的虛線箭頭，就是第10行，L.r[j-1]=L.r[j]的過程，將5右移一位。

4)?此時，第10行就是在移動完成后，空出了空位，然后第11 行L.r[j+1]=L.r[0]，將哨兵的3賦值給j=0時的L.r[j+1]，也就是說，將撲克牌3放放置到L.r[1]的位置。如圖9-5-3。

5)?繼續循環，第6行，因為此時i=3，L.r[i]=4比L.r[i-1]=5要小，因此執行第8～11行的操作。將5再右移一位，將4放置到當前5所在位置。如圖9-5-4。

6)?再次循環，此時i=4。因為L.r[i]=6比L.r[i-1]=5要大，于是第8～11行代碼不執行，此時前三張牌的位置沒有變化。如圖9-5-5。
?

7)?再次循環，此時i=5，因為L.r[i]=2比L.r[i-1]=6要小，因此執行第8～11行的操作。由于6、5、4、3都比2小，它們都將右移一位，將2放置到當前3所在位置。如圖9-5-6。此時我們的排序也就完成了。

9.5.2?直接插入排序復雜度分析

??????? 我們來分析一下這個算法，從空間上來看，它只需要一個記錄的輔助空間。因此關鍵是看它的時間復雜度。
??????? 當最好的情況，也就是要排序的表本身就是有序的，比如紙牌拿到后就是{2,3,4,5,6}，那么我們比較次數，其實就是代碼第6行每個L.r[i]與L.r[i-1的比較，共比較了?次，由于每次都是L.r[i]>L.r[i-1]，因此沒有移動的記錄，時間復雜度為O(n)。
??????? 當最壞的情況，即待排序表是逆序的情況比如{6,5,4,3,2}，此時需要比較?次，而記錄的移次數也達到最大值?次。
??????? 如果排序記錄是隨機的，那么根據概率相同的原則，平均比較和移動次約為n²/4 次。因此，我們得出直接插入排序法的時間復雜度為O(n²)。從這里也看出，同樣的O(n²)時間復雜度，直接插入排序法比冒泡和簡單選擇排序的性能要好一些。

出處：http://www.cnblogs.com/cj723/archive/2011/04/19/2020501.html

總結

以上是生活随笔為你收集整理的《大话数据结构》第9章 排序 9.5 直接插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。