一種最簡單的排序方法直接插入排序01簡介過程實例哨兵的作用算法描述目錄030204基本信息直接插入排序（StraightInsertionSort）是一種最簡單的排序方法，其基本操作是將一條記錄插入到已排好的有序表中，從而得到一個新的、記錄數量增1的有序表。簡介引言基本思想算法思想排序方法簡介引言在日常生活中，經常碰到這樣一類排序問題：把新的數據插入到已經排好的數據列中。例如：一組從小到大排好順序的數據列{1,2,3,4,5,6,7,9,10}，通常稱之為有序列，我們用序號1,2,3，…表示數據的位置，欲把一個新的數據8插入到上述序列中。完成這個工作的步驟：①確定數據“8”在原有序列中應該占有的位置序號。數據“8”所處的位置應滿足小于或等于該位置右邊所有的數據，大于其左邊位置上所有的數據。②將這個位置空出來，將數據“8”插進去。直接插入排序(straightinsertionsort)的做法是：每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。第一趟比較前兩個數，然后把第二個數按大小插入到有序表中；第二趟把第三個數據與前兩個數從后向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。直接插入排序是由兩層嵌套循環組成的。外層循環標識并決定待比較的數值。內層循環為待比較數值確定其最終位置。直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環是從第二個數值開始的。基本思想每一趟將一個待排序的記錄，按其關鍵字的大小插入到已經排好序的一組記錄的適當位置上，直到所有待排序記錄全部插入為止。

待排序記錄R1，R2，…，Rn–1,Rn第一步：R1第二步：(R1),R2第三步：(R1,R2),R3……第j步：(R1，R2，…，Rj–1),Rj……第n步:(R1，R2，…，Rn–1),Rn．例：j=5算法思想算法InsertSort(R,n)FORj=2TOnDO(//每次將Rj插入到有序表R1，…，Rj–1中K←Kj.R←Rj.i←j-1.WHILE(i>0)AND(Ki>K)DO(Ri+1←Ri.i←i-1.)Ri+1←R.)算法InsertSortA(R,s,e)//引入虛擬記錄,Ks-1≤min{Ki|s≤i≤e}排序方法1．簡單方法首先在當前有序區R[1..i-1]中查找R[i]的正確插入位置k(1≤k≤i-1)；然后將R[k．．i-1]中的記錄均后移一個位置，騰出k位置上的空間插入R[i]。注意：若R[i]的關鍵字大于等于R[1．．i-1]中所有記錄的關鍵字，則R[i]就是插入原位置。2．改進的方法一種查找比較操作和記錄移動操作交替地進行的方法。具體做法：將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=i-1，i-2，…，1)的關鍵字進行比較：①若R[j]的關鍵字大于R[i]的關鍵字，則將R[j]后移一個位置；②若R[j]的關鍵字小于或等于R[i]的關鍵字，則查找過程結束，j+1即為R[i]的插入位置。關鍵字比R[i]的關鍵字大的記錄均已后移，所以j+1的位置已經騰空，只要將R[i]直接插入此位置即可完成一趟直接插入排序。哨兵的作用哨兵的作用算法中引進的附加記錄R稱監視哨或哨兵(Sentinel)。哨兵有兩個作用：①進入查找(插入位置)循環之前，它保存了R[i]的副本，使不致于因記錄后移而丟失R[i]的內容；②它的主要作用是：在查找循環中"監視"下標變量j是否越界。一旦越界(即j=0)，因為R.可以和自己比較，循環判定條件不成立使得查找循環結束，從而避免了在該循環內的每一次均要檢測j是否越界(即省略了循環判定條件"j>=1")。注意：①實際上，一切為簡化邊界條件而引入的附加結點(元素)均可稱為哨兵。【例】單鏈表中的頭結點實際上是一個哨兵②引入哨兵后使得測試查找循環條件的時間大約減少了一半，所以對于記錄數較大的文件節約的時間就相當可觀。對于類似于排序這樣使用頻率非常高的算法，要盡可能地減少其運行時間。所以不能把上述算法中的哨兵視為雕蟲小技，而應該深刻理解并掌握這種技巧。過程實例過程實例例：原有序表：(915232837)20找插入位置:(915^232837)20新有序表:(91520232837)設待排序的文件有8個記錄，其關鍵字分別為：49，38，65，97，76，13，27，49。為了區別兩個相同的關鍵字49