折半插入排序

#include<stdio.h>#include<stdlib.h>#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ int*elem; intlength; intlistsize;}SqList;voidInitList(SqList&L);voidInput(SqList&L);voidBInsertSort(SqList&L);voidOutput(SqListL);voidmain(){ SqListL; InitList(L); Input(L); BInsertSort(L); Output(L);}voidInitList(SqList&L){ L.elem=(int*)malloc((LIST_INIT_SIZE+1)*sizeof(int)); if(!L.elem) exit(-1); L.length=0; L.listsize=LIST_INIT_SIZE;}voidInput(SqList&L){inta=1,i=1; while(a) { printf("请输入数据(输入0结束):"); scanf("%d",&a); if(a) { if(L.length>=L.listsize) { L.elem=(int*)malloc((LIST_INIT_SIZE+1+LISTINCREMENT)*sizeof(int)); L.listsize+=LISTINCREMENT; } if(!L.elem) exit(-1); L.elem[i]=a; i++; L.length++; } }}voidBInsertSort(SqList&L){ inti,j,low,high,m; for(i=2;i<L.length+1;i++) { L.elem[0]=L.elem[i]; low=1;high=i-1; while(low<=high) { m=(low+high)/2; if(L.elem[0]<L.elem[m]) high=m-1; else low=m+1; } for(j=i-1;j>=high+1;j--) L.elem[j+1]=L.elem[j]; L.elem[high+1]=L.elem[0]; }}voidOutput(SqListL){ inti; system("cls"); printf("顺序L作直接插入排序后的次序为:"); for(i=1;i<L.length+1;i++) printf("%d",L.elem[i]); printf("\n\n\n\n\n\n\n\n\n\n\n\n");}