数据结构实验（C语言）：折半插入排序、快速排序
文章参考过网上的内容如有侵权请联系#includestdio.h#includestdlib.htypedefstruct{int*data;//线性链表的初值intlength;}Sqlist;intPartition2(SqlistL,intlow,inthigh){//交换顺序表L中子表r[low..high]的记录枢纽记录到位并返回其所在位置//在它之前后的记录均不大小于它L.data[0]L.data[low];//用子表第一个记录作枢纽记录intkeyL.data[low];//枢纽记录关键字while(lowhigh){while(lowhighL.data[high]key)--high;//从右向左搜索L.data[low]L.data[high];//移动比枢纽记录值小的记录while(lowhighL.data[low]key)low;//从左往右搜索L.data[high]L.data[low];//将比枢纽记录大的记录移到高端}L.data[low]L.data[0];returnlow;}voidQsort(SqlistL,intlow,inthigh){//对顺序表L中的子序列L.r[low..high]作快速排序if(lowhigh){//长度大于一intpivotlocPartition2(L,low,high);//将子序列一分为二Qsort(L,low,pivotloc-1);//对低子表递归排序Qsort(L,pivotloc1,high);//对高子表递归排序}}voidBInserSort(SqlistL){//对顺序表L作折半插入排序inti;for(i2;iL.length;i){L.data[0]L.data[i];//将L.r[i]暂存到L.r[0]intlow1;inthighi-1;while(lowhigh){//在序列中折半查找插入位置intm(lowhigh)/2;if(L.data[0]L.data[m])highm-1;//插入点在低半区elselowm1;//插入点在高半区}for(intji-1;jhigh1;--j)L.data[j1]L.data[j];//记录后移L.data[high1]L.data[0];//插入}}intmain(){inta[8]{0,1,6,4,10,5,3,2};Sqlist L;L.length7;L.dataa;for(inti1;iL.length;i)printf(%d ,L.data[i]);printf(\n);printf(-----------进行快速排序--------\n);Qsort(L,1,7);for(inti1;iL.length;i)printf(%d ,L.data[i]);printf(\n);printf(-------进行折半插入排序---------\n);BInserSort(L);for(inti1;iL.length;i)printf(%d ,L.data[i]);}
