直接插入排序的进阶功法
折半插入排序的算法讲解:（默认为升序）
本质：折半插入排序利用二分法进行寻找待插入元素的位置，是直接插入排序的一种改进。
小伙伴们，如果对直接插入排序有问题，可以看小编的这一篇：
折半查找规则：假设数组的名字为a
利用三个下标 low high mid
low 一开始为 0 high 一开始为数组长度减一
mid = (low+high) /2
利用 a[mid]和待插入元素进行比较
如果 a[mid] > 待插入元素 high = mid -1
a[mid] < 待插入元素时 low = mid + 1
直到 low > high 结束 得到插入元素的位置
当排序列中不含有待插入元素
| low |
high |
mid |
和插入的元素的比较（val） |
| 0 |
4 |
2 |
a[2] = 5 5< 7 low = mid +1 |
| 3 |
4 |
3 | a[3] = 9 9 > 7 high = mid -1 |
| 3 |
2 |
low > high 结束 待插元素的位置 high+1 |
| low |
high |
mid |
和插入的元素的比较（val） |
| 0 |
4 |
2 |
a[2] = 5 5> -1 high = mid -1 |
| 0 |
1 |
0 |
a[0] = 0 0 > -1 high = mid -1 |
| 0 | -1 |
low > high 结束 待插元素的位置 high+1 |
| low |
high |
mid |
和插入的元素的比较（val） |
| 0 |
4 |
2 |
a[2] = 5 5< 15 low = mid +1 |
| 3 |
4 | 3 | a[3] = 9 9 <15 low = mid +1 |
| 4 | 4 |
4 |
a[4] = 10 10<15 low = mid +1 |
| 5 | 4 | low > high 结束 待插元素的位置 high+1 |
结论：待插入元素的位置都是 high+1
当排序列中含有待插入元素
利用稳定性和时间复杂度的考虑，我们为上面的规则折半算法规则进行改进
折半查找规则：假设数组的名字为a
利用三个下标 low high mid
low 一开始为 0 high 一开始为数组长度减一
mid = (low+high) /2
利用 a[mid]和待插入元素进行比较
如果 a[mid] >= 待插入元素 high = mid -1
a[mid] < 待插入元素时 low = mid + 1
直到 low > high 结束 得到插入元素的位置
| low |
high |
mid |
和插入的元素的比较（val） |
| 0 |
4 |
2 |
a[2] = 5 5== 5 low = mid +1 |
| 3 |
4 | 3 | a[3] = 5 5==5 low = mid +1 |
| 4 | 4 | 4 | a[4] = 10 10>5 high = mid -1 |
| 4 |
3 |
low > high 结束 待插元素的位置 high+1 |
结论：插入元素的位置都是 high+1
总结：元素的位置都是 high+1 得到插入位置就可以写代码了
//折半插入排序void binarysort(int * a,int length,int val);/*a 指针变量 接受数组的首地址length 数组的长度val 待插入的元素*/void sort(int * a,int length);void traversal(int * a,int length);int main(void){int a[5] = {2,-5,3,1,10};sort(a,5);traversal(a,5);return 0;}void binarysort(int * a,int length,int val){int low = 0;int high = length-1;int mid ;int i;while(low<=high){mid = (low+high)/2;if(a[mid]<=val){low = mid+1;}else{high = mid-1;}}for(i=length-1;i>=high+1;--i){a[i+1] = a[i];}a[high+1] = val;return;}void sort(int * a,int length){int i ;for(i=1;i<length;++i){binarysort(a,i,a[i]);}return;}void traversal(int * a,int length){int i ;for(i=0;i<length;++i){printf("%d ",a[i]);}printf("\n");return;}