插入排序（直接插入）
void insertsort(int a[],int n) { int temp; int i,j; for(i=1;i<n;i++) { temp=a[i]; j=i-1; while(j>=0&&temp<a[j]) { a[j+1]=a[j]; j--; } a[j+1]=temp; } }
空间复杂度O（1），时间复杂度O（n^2）
void insertsort1(int a[],int n) { int i,j,low,high,mid,temp; for(i=1;i<n;i++) { temp=a[i]; low=0;high=i-1; while(low<=high) { mid=(low+high)/2; if(temp<a[mid]) { high=mid-1; } else { low=mid+1; } } for(j=i-1;j>=high+1;j--) { a[j+1]=a[j]; } a[high+1]=temp; } }
空间复杂度O（1），时间复杂度O（n^2）
希尔排序
void ShellSort(int a[],int n) { int i,j,gap,temp; gap=n/2; while(gap>0) { for(i=gap;i<n;i++) { temp=a[i]; j=i-gap; while(j>=0&&temp<a[j]) { a[j+gap]=a[j]; j=j-gap; } a[j+gap]=temp; } gap=gap/2; } }
空间复杂度为O（1），时间复杂度为O（n^1.3）
