二分直接插入排序

普通的直接插入排序如果在最复杂的情况下，所要排序的整个数列是逆序的，当第 i-1 趟需要将 第 i 个元素插入前面的 0~ i -1 个元素的序列当中的时候，它总是会从第 i -1 个元素开始，逐个比较每个元素的大小，直到找到相应的位置。 这个算法中丝毫没有考虑当要插入第 i 个元素时前面的 0~~ i -1 序列是有序的这个特点。今天要总结的这个算法就充分的利用了这一点。

算法的基本过程：

(1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半； (2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方； (3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

时间复杂度：

折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（N^2），在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。

空间复杂度：

折半插入排序和插入排序一样只需要一个多余的缓存数据单元来放第 i 个元素，所以空间复杂度是O（1），因为排序前2个相等的数在序列的前后位置顺序和排序后它们两个的前后位置顺序相同，所以它是一个稳定排序。 #include<stdio.h> void printArray(int a[], int size) //打印数组元素 { int i; for(i = 0; i < size; i++) printf("%d ",a[i]); printf("\n"); } void bubble_sort(int a[], int size){ int i,j,mid,temp,low,high; for(i = 1;i<size;i++)//默认a[0]是有序的 { low = 0,high = i - 1; while(low <= high) { mid = (low + high) / 2;//不断的寻找中间值 if (a[i] < a[mid])//如果小于中间值 high = mid - 1;//在小于中间值的部分查找 else low = mid + 1;//在大于中间值的部分查找 } temp = a[i]; for(j = i;j > low;j--)//将low以后的元素（包括low）数组后移动 a[j] = a[j - 1]; a[low] = temp; printArray(a,size); } } int main() { int count=9,a[9]={2,1,3,8,6,5,7,4,2}; printArray(a,count); bubble_sort(a,count); }