共计 680 个字符,预计需要花费 2 分钟才能阅读完成。
#include <iostream>
using namespace std;
#define MAXSIZE 20
typedef struct{
int key;
char *otherinfo;
}ElemType;
typedef struct{
ElemType *r;
int length;
}SqList;
// 折半插入排序
void BInsertSort(SqList &L){
int i,j,low,high,m;
for(i=2;i<=L.length;++i){L.r[0]=L.r[i];
low=1; high=i-1;
while(low<=high){m=(low+high)/2;
if(L.r[0].key<L.r[m].key) high=m-1;
else low=m+1;
}
for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
void Create_Sq(SqList &L){
int i,n;
cout<<"数据个数:";
cin>>n;
cout<<"待排序的数据:";
for(i=1;i<=n;i++){cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L){
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i].key<<" ";
}
int main(){
SqList L;
L.r=new ElemType[MAXSIZE+1];
L.length=0;
Create_Sq(L);
BInsertSort(L);
cout<<"折半插入排序:";
show(L);
}
正文完