排序算法二：二分（折半）插入排序算法
声明：引用请注明出处
引言
在我的博文《“主宰世界”的10种算法短评》中给出的首个算法就是高效的排序算法。本文将对排序算法做一个全面的梳理，，从最简单的“冒泡”到高效的堆排序等。
上一篇博文《排序算法一：直接插入排序》讲述了直接插入排序，本文讲述另一种插入排序算法：二分（折半）插入排序。
排序相关的的基本概念排序：将一组杂乱无章的数据按一定的规律顺次排列起来。 数据表( data list): 它是待排序数据对象的有限集合。排序码(key):通常数据对象有多个属性域，即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。分类 内排序：指在排序期间数据对象全部存放在内存的排序；外排序：指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序算法的分析排序算法的稳定性
如果在对象序列中有两个对象 的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
排序算法的评价时间开销排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算空间开销
算法执行时所需的附加存储。
二分（折半）插入排序基本思想
设在顺序表中有一个对象序列的插入位置。关于二分搜索法在我的博文《》中有精彩论述，这里只是简要的说明一下二分搜索在二分插入排序中的应用。
二分插入排序图示
第一行是原始数据，第二行是假设已经排好了前，其余数据往后移动一个位置。
二分插入排序算法分析C代码实现binarySearch(int a[], int item, int low, int high){if (high <= low)return (item > a[low])? (low + 1): low;int mid = (low + high)/2;if(item == a[mid])return mid+1;if(item > a[mid])return binarySearch(a, item, mid+1, high);return binarySearch(a, item, low, mid-1);}// Function to sort an array a[] of size ‘n’void insertionSort(int a[], int n){int i, loc, j, k, selected;for (i = 1; i < n; ++i){j = i – 1;selected = a[i];// find location where selected sould be inseretdloc = binarySearch(a, selected, 0, j);// Move all elements after location to create spacewhile (j >= loc){a[j+1] = a[j];j–;}a[j+1] = selected;}}// Driver program to test above functionint main(){int a[] = {37, 23, 0, 17, 12, 72, 31,46, 100, 88, 54};int n = sizeof(a)/sizeof(a[0]), i;insertionSort(a, n);printf(“Sorted array: \n”);for (i = 0; i < n; i++)printf(“%d “,a[i]);return 0;}
2015-9-24 艺少
吃水不忘挖井人。
