主题:[讨论]折半查找插入的小问题。
折半查找插入算法中,折半查找插入位置,是不是查找到插入位置后low=high+1 ?
下面是具体算法.
typedef int KeyType; //定义关键字类型为整数类型
typedef struct {
KeyType key; //关键字项
InfoType otherinfo; //其他数据项
}RedType; //记录类型
typedef struct {
RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元
int length; //顺序表长度
}SqList;
void BinsertSort (SqList &L) {
for (i=2;i<=L.length; ++i) {
L.r[0]=L.r[i]; //将L.r[i]暂存到L.r[0]
low=1; high=i-1;
while(low<high) { //在r[low..high]中折半查找有序插入的位置
m=(low+high)/2; //折半
if (LT(L.r[0].key, L.r[m].key)) high=m-1; //插入点在低半区
else low=m+1; //插入点在高半区
}//while
for (j=i-1; j>=high+1; --j ) L.r[j+1]=L.r[j]; //记录后移
L.r[high+1]=L.r[0]; //插入
}//for
}//BInsertSort
我个人看来查到到位置以后low=high+1的,所以for (j=i-1; j>=high+1; --j )也可以把high+1用low代替.但不知道有没有遗漏什么..
求教了...
下面是具体算法.
typedef int KeyType; //定义关键字类型为整数类型
typedef struct {
KeyType key; //关键字项
InfoType otherinfo; //其他数据项
}RedType; //记录类型
typedef struct {
RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元
int length; //顺序表长度
}SqList;
void BinsertSort (SqList &L) {
for (i=2;i<=L.length; ++i) {
L.r[0]=L.r[i]; //将L.r[i]暂存到L.r[0]
low=1; high=i-1;
while(low<high) { //在r[low..high]中折半查找有序插入的位置
m=(low+high)/2; //折半
if (LT(L.r[0].key, L.r[m].key)) high=m-1; //插入点在低半区
else low=m+1; //插入点在高半区
}//while
for (j=i-1; j>=high+1; --j ) L.r[j+1]=L.r[j]; //记录后移
L.r[high+1]=L.r[0]; //插入
}//for
}//BInsertSort
我个人看来查到到位置以后low=high+1的,所以for (j=i-1; j>=high+1; --j )也可以把high+1用low代替.但不知道有没有遗漏什么..
求教了...