折半插入排序(C语言版).doc

《折半插入排序(C语言版).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、折半查找插入排序1.实验目的本实验将通过实验实例和程序设计练习，达到如下目的：通过实验掌握二分排序的基本概念，掌握二分排序的基本思想和算法实现。2.实验内容本实验的内容包括：设计一个算法用二分查找实现插入排序的“寻找插入位置”操作。3.实验要求二分查找：在有序表中进行，先确定表的中点位置，再通过比较确定下一步查找哪个半区。以下是我根据严蔚敏教材数据结构（C语言版）自己编写的程序，在程序运行时根据提示随便输入一组数，并以-1结束，程序在TC2.01版本上运行无误，#include

2、#defineMAX100typedefstruct{intelem[MAX];intlength;}SSTable;voidBInsertSort(SSTable*L);intmain(){intm,i=1,a,k;SSTableST;printf("Pleaseinputthosenumbersandpress"-1"toend!");scanf("%d",&a);while(a!=-1){ST.elem[i++]=a;scanf("%d",&a);}ST.length=i-1;BI

3、nsertSort(&ST);printf("Theresultis:");for(m=1;m<=ST.length;m++)printf("%5d",ST.elem[m]);getch();}voidBInsertSort(SSTable*L){inti,low,high,m,j;for(i=2;i<=(L->length);++i){(*L).elem[0]=(*L).elem[i];low=1;high=i-1;while(low<=high){m=(low+high)/2;if((*

4、L).elem[0]<(*L).elem[m])high=m-1;elselow=m+1;}for(j=i-1;j>=high+1;--j)(*L).elem[j+1]=(*L).elem[j];(*L).elem[high+1]=(*L).elem[0];}}