插入排序的准則是在有序序列中插入新的記錄以達到擴大有序區的長度的目的一趟直接插入排序的基本思想則是:在對記錄序列R[n]的排序過程中區段R[i]中的記錄已按關鍵字非遞減的順序排列將R[i]插入到有序序列R[i]中使區段R[i]中的記錄按關鍵字非遞減順序排列
由此實現一趟插入排序的步驟為
)在R[i]中查找R[i]的插入位置即確定j(≤j＜i)使得R[j]key≤R[i]key＜R[j+i]key
)將R[j+i]中的記錄後移一個位置
)將R[i]插入到j+的位置
和順序查找類似為了避免在查找過程中判別循環變量是否出界設置R[]為監視哨並在查找的同時進行記錄後移如下演示所示
From:http://tw.wingwit.com/Article/program/sjjg/201311/23901.html
