插入排序

插入排序基本形式

 1 //c
 2 
 3 typedef int elemtype;
 4 void InsertSort(elemtype *a,int n){
 5     int j;
 6     elemtype tmp;
 7     for(int i=1;i<n;i++){
 8         tmp=a[i];
 9         for(j=i;j>0&&tmp<a[j-1];j--)
10             a[j]=a[j-1];
11         a[j]=tmp;
12     }
13 }

 1 # python3
 2 
 3 def InsertSort(lst,n):
 4   for i in range(1,n):
 5     tmp=lst[i]
 6     for j in range(i,-1,-1):
 7       if j==0 or tmp>=lst[j-1]:
 8         break
 9       lst[j]=lst[j-1]
10     lst[j]=tmp
11 
12     
13 lst=[4,3,2,6,7,8,4,3,-4,0]
14 InsertSort(lst,len(lst))
15 print(lst)

在向前插入的过程中，因为前面已经有序

则在寻找插入位置时可以选择折半查找法

此时插入排序可改进为折半插入排序