插入排序 && 折半插入排序 && 希尔排序：
（一）插入排序：
（1）代码实现：
void insertSort(int *array,int n){
int temp;
int i,j; for(i=1;i<n;i++){
if(array[i]<array[i-1]){
temp=array[i]; for(j=i-1;j>=0 && array[j]>array[i]; j--)
array[j+1]=array[j]; array[j+1]=temp;
} }
}（2）最好最坏分析：
插入排序的时间复杂度严重依赖于待排序元素的初始序列；
1）最好情况下：如果待排序的初始序列已经从小到大排序，每次插入元素只需要与有序序列的最后一个元素比较1次即可，总的比较次数为n-1,元素的移动次数为0.时间复杂度为O(n);
2）最坏情况下：如果待排序的序列已经是从大到小的序列，则时间复杂度为O(n^2);
（3）插入排序的稳定性分析：
因为每次比较，如果逆序都是把大者后移；如果相等，不执行这种操作，所以不会原来在后面的反而被移动到前面来了的现象。
注意：如果把比较temp<a[j],错误的写为temp<=a[j],则就是不稳定的排序。
--------------------------
（二）折半插入排序：
（1）思想：
a[0~i-1]以及排序后，在插入a[i]时，利用折半插入的方法，在有序序列a[0~i-1]中寻找a[i]的插入位置、
为了保证稳定，应该在a[0~i-1]中找到<=a[i]的最后一个位置.
所以需要注意二分查找中的边界处理。
（1-2）因为是在有序序列a[0~i-1]中，寻找到<=temp的最后一个元素的位置，所以缩小左边界的位置，即low=mid+1。
如：
1)查找到>=temp的第一个位置；由于第一个位置相当于是左区间，所以应该是左区间改变，即left=mid+1,当temp>=array[mid]时。
while(left<=right){
mid=(right-left)/2+left; if(temp>=array[mid])
}（2）代码实现：
/*
从小到大排序;*/
void binaryInsertSort(int * array,int n){
int temp;
int i,j;
int low ,high,mid; for(i=1;i<n;i++){
if(array[i]<array[i-1]){
temp=array[i];
low=0;
high=i-1; while(low<=high){
mid=(high-low)/2+low; if(array[mid]<=temp)
low=mid+1; else high=mid-1;
} for(j=i-1;j>=low;j--)
array[j+1]=array[j]; array[j+1]=temp;
}
}
}
（3）二分插入排序的稳定性分析：
分析：
如果查找元素比中间的元素小，则查找区间缩小到左半部分，否则，查找区间缩小到右半区间，
如果查找元素等于中间元素，则要在中间元素的右区间查找。
注意：如果将array[mid]<=temp写为array[mid]<temp,则不是稳定的排序。
（4）折半插入排序的复杂度分析：
1.比较次数：
插入第i个元素时，比较次数大约为O(lgi),所以总的比较次数为 lgi (i 从1到n-1)之和=lg(n!)=nlgn
2.移动次数：
O(n^2)
------------------
（三）shell排序：（缩小增量排序）
（1）思想：
1）每趟按照一个增量gap作为间隔，将全部元素序列分为gap个子序列，所有距离为gap的元素放到同一个子序列中，在每个子序列中使用直接插入排序。
2）不断的缩小gap,知道最后的gap=1,即只有一个子序列。
时间复杂度为O(n^1.3)
（2）代码实现：
//从start开始，间隔为gap的子序列进行插入排序。
void insertSort(int * array ,int n ,int start ,int gap){
int temp;
int i,j; for(i=start+gap;i<n;i++){
if(array[i]<array[i-gap]){
temp=array[i];
j=i-gap; for(;j>=start && array[j]>temp;j=j-gap)
array[j+gap]=array[j]; array[j+gap]=temp;
}
}
}void shellSort(int *array ,int n){
int gap=n/2;//将大 的序列分为gap个小序列且每个小序列中的两个相邻的元素之间的间隔为gap; while(gap>=1){
for(int k=0;k<gap;k++){//gap个子序列，每个子序列进行直接插入排序，并且每个子序列的起始地址为k。
insertSort(array,n,k,gap);
} gap=gap/2;
}
}
（3）注意：shellSort是不稳定的排序。
-------