直接插入排序
穩定的排序方法之一
直接插入排序(Straight Insertion Sort)是一種最簡單的排序方法,其基本操作是將一條記錄插入到已排好的有序表中,從而得到一個新的、記錄數量增1的有序表。
在日常生活中,經常碰到這樣一類排序問題:把新的數據插入到已經排好的數據列中。例如:一組從小到大排好順序的數據列{1,2,3,4,5,6,7,9,10},通常稱之為有序列,我們用序號1,2,3,…表示數據的位置,欲把一個新的數據8插入到上述序列中。
完成這個工作的步驟:
①確定數據“8”在原有序列中應該佔有的位置序號。數據“8”所處的位置應滿足小於或等於該位置右邊所有的數據,大於其左邊位置上所有的數據。
②將這個位置空出來,將數據“8”插進去。
直接插入排序(straight insertion sort)的做法是:
每次從無序表中取出第一個元素,把它插入到有序表的合適位置,使有序表仍然有序。
第一趟比較前兩個數,然後把第二個數按大小插入到有序表中;第二趟把第三個數據與前兩個數從後向前掃描,把第三個數按大小插入到有序表中;依次進行下去,進行了(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
原有序表中關鍵詞比Rj大的記錄數:dj
比較次數:dj+1 移動次數: dj+2
演演算法 InsertSort (R,n)
FOR j=2 TO n DO
( //每次將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}
ISA1 [逐一排序]
FOR j=s+1 TO e DO
( i←j-1.K←Kj. R←Rj .
WHILE K
( Ri+1←Ri .
i←i-1 .)
Ri+1←R .
)
ISA1 [逐一排序]
FOR j=s+1 TO e DO
( i←j-1.K←Kj . R←Rj .
WHILE K
( Ri+1←Ri .i←i-l ) .
Ri+1←R )
直接插入排序的時間複雜度為 O(n2)。
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[0]稱監視哨或哨兵(Sentinel)。
哨兵有兩個作用:
① 進人查找(插入位置)循環之前,它保存了R[i]的副本,使不致於因記錄后移而丟失R[i]的內容;
② 它的主要作用是:在查找循環中"監視"下標變數j是否越界。一旦越界(即j=0),因為R[0].可以和自己比較,循環判定條件不成立使得查找循環結束,從而避免了在該循環內的每一次均要檢測j是否越界(即省略了循環判定條件"j>=1")。
注意:
① 實際上,一切為簡化邊界條件而引入的附加結點(元素)均可稱為哨兵。
【例】單鏈表中的頭結點實際上是一個哨兵
② 引入哨兵后使得測試查找循環條件的時間大約減少了一半,所以對於記錄數較大的文件節約的時間就相當可觀。對於類似於排序這樣使用頻率非常高的演演算法,要儘可能地減少其運行時間。所以不能把上述演演算法中的哨兵視為雕蟲小技,而應該深刻理解並掌握這種技巧。
例:
原有序表:(9 15 23 28 37) 20
找插入位置 : (9 15 ^ 23 28 37) 20
新有序表: (9 15 20 23 28 37)
設待排序的文件有8個記錄,其關鍵字分別為:49,38,65,97,76,13,27,49。為了區別兩個相同的關鍵字49,后一個49的下方加了一下劃線以示區別。
Python 代碼實現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #!/usr/bin/env python3 # coding = utf-8 # 適合初學者版: def InsertSort(list): n = len(list) for i in range(1, n): j = i while j > 0: if list[j] < list[j - 1]: list[j - 1], list[j] = list[j], list[j - 1] j = j - 1 else: break return list # 進階版 def InsertSort2(list): for i in range(1, len(list)): for j in range(i): if list[i] < list[j]: list.insert(j, list[i]) # 首先碰到第一個比自己大的數字,趕緊剎車,停在那,所以選擇insert list.pop(i + 1) # 因為前面的insert操作,所以後面位數+1,這個位置的數已經insert到前面去了,所以pop彈出 break return list if __name__ == '__main__': list = [23, 32, 69, 16, 37, 73] print(list) print(InsertSort(list)) print(InsertSort2(list)) |
C/C++代碼實現直接插入排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include using namespace std; int main() { int a[]={98,76,109,34,67,190,80,12,14,89,1}; int k=sizeof(a)/sizeof(a[0]); int i,j; |
1 |
Objective-C實現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | +(void)sort:(NSMutableArray*)array { inti,y; for(i=0;i<[arraycount]-1;i++) { //前面一位大於後面一位 if([[arrayobjectAtIndex:i+1]intValue]<[[arrayobjectAtIndex:i]intValue]) { //保存後面一位 NSString*temp=[arrayobjectAtIndex:i+1]; //從后一位開始 for(y=i+1;y>0&&[[arrayobjectAtIndex:y-1]intValue]>[tempintValue];y--){ [arrayexchangeObjectAtIndex:y-1withObjectAtIndex:y]; } //[arrayremoveObjectAtIndex:y]; //[arrayinsertObject:tempatIndex:y]; } } } |
JAVA實現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | public class InsertSort{ public void insertSort(int[] array){ for(int i=1;i { if(array[i] { int temp=array[i];//保存第i位的值 int j = i - 1; while(j>=0 && temp { array[j+1]=array[j]; j--; } array[j+1]=temp;//插入第i位的值 } } } public static void printArray(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i]); if (i != array.length - 1) { System.out.print(","); } } } } |
C#實現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | public void Action(int[]array) { for(int i=1; i { if(array[i] { int temp=array[i]; int j=0; for(j=i-1;j>=0 && temp { array[j+1]=array[j]; } array[j+1]=temp; } } } PHP實現 function Insert_Sort($myarr) { $temp=0; for($i=1;$i { $temp=$myarr[$i]; $j=$i-1; while($j>=0&&$temp<$myarr[$j]) { $myarr[$j+1]=$myarr[$j]; $j--; } $myarr[$j+1]=$temp; } } print_r($myarr); echo ' '; Insert_Sort($myarr); |
目錄