折半插入排序的算法分析，折半插入排序

?

问题：

对待排序的数组r[1..n]中的元素进行直接插入排序，得到一个有序的（从小到大）的数组r[1..n]。

算法思想：

1、设待排序的记录存放在数组r[1..n]中，r[1]是一个有序序列。

2、循环n-1次，每次使用折半查找法，查找r[i]（i=2，..，n）在已排好的序列r[1..i-1]中的插入位置，然后将r[i]插入表长为i-1的序列r[1..i-1]，直到将r[n]插入表长为n-1的有序序列r[1..n-1],最后得到一个表长为n的有序序列。

图解：

?

代码：

#includeusing namespace std;#define MAXSIZE 20//顺序表的最大长度typedef int KeyType;//定义关键字类型为整型typedef int InfoType;typedef struct{ KeyType key;//关键字项 InfoType otherinfo;//其他数据项}RedType;typedef struct{ RedType r[MAXSIZE+1];//r[0]闲置或做哨兵单元 int length;//顺序表的长度}SqList;//顺序表类型void BInsertSort(SqList &L)//对顺序表L做折半插入排序{ int low,high,m; for(int i=2;i