写出实现折半插入排序的算法或程序代码。
写出实现折半插入排序的算法或程序代码。
参考答案和解析
//算法8.2 折半插入排序#include using namespace std;#define MAXSIZE 20 //顺序表的最大长度typedef struct{int key;char *otherinfo;}ElemType;//顺序表的存储结构 typedef struct{ ElemType *r; //存储空间的基地址 int length; //顺序表长度}SqList;//顺序表void BInsertSort(SqList &L){//对顺序表L做折半插入排序int i,j,low,high,m;for(i=2;i{L.r[0]=L.r[i]; //将待插入的记录暂存到监视哨中low=1; high=i-1; //置查找区间初值while(low{//在r[low..high]中折半查找插入的位置m=(low+high)/2; //折半if(L.r[0].key//插入点在前一子表else low=m+1; //插入点在后一子表}//whilefor(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//将r[0]即原r[i]，插入到正确位置 }//for}//BInsertSortvoid Create_Sq(SqList &L){int i,n;coutcin>>n;//输入个数coutwhile(n>MAXSIZE){coutcin>>n;}for(i=1;i{cin>>L.r[i].key;L.length++;}}void show(SqList L){int i;for(i=1;icout}void main(){SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);BInsertSort(L);coutshow(L);}
相关考题：
排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）A、折半插入排序B、直接插入排序C、归并排序D、选择排序
单选题排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）A折半插入排序B直接插入排序C归并排序D选择排序
填空题完成下列折半插入排序算法。 Void binasort（struct node r[MAXSIZE]，int n） {for（i=2；i else low=mid+1 ； } for（j=i-1；j=low；j- -）r[j+1]=r[j] ； r[low]=（） ； } }
多选题数据结构与算法里，以下算法时间复杂度是O（n*n）的是（）。A冒泡排序B直接插入排序C折半查找D希尔排序