课程设计——内部排序算法比较(4)

数据结构课程设计

b[j+1]=b[0]; s++; }

cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl; }

3.2 折半排序

由于插入排序的基本操作是在一个有序表中进行查找和插入，可知这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序，其算法如下：

void BInsertSort (int *data,long *p_movetime ,long *p_comparetime){

int i ,j ,amount,low,high,m;

(*p_comparetime)++; //针对于接下来的*(data)和*(data+m)的

for( i = 2;i <=amount; ++i){

*(data) = *(data+i); (*p_movetime)++; low = 1; high = i-1;

while(low<=high){

(*p_comparetime)++; m = (low+high)/2;

*p_movetime = *p_comparetime = 0; amount = *data;

比较

if( *(data) < *(data+m)) high = m-1; else low = m+1;

4