实现直接插入排序-二分法插入排序、希尔排序-冒泡排序-快速排序-直接选择排序的算法

#includestdio.h#defineMax100//数组长度typedefstruct{intkey;//关键字chardata;//其他字段}LineList;//线性表的类型voidBubbleSort(LineListR[],intn){inti,j,exchange;LineListtemp;for(i=0;in-1;i++){exchange=0;for(j=n-1;ji;j--)//比较找出最小记录if(R[j].keyR[j-1].key){//比较移行temp=R[j];R[j]=R[j-1];R[j-1]=temp;exchange=1;}if(exchange==0)//交换结束后结束return;}}/*直接插入排序，升序*/voidStraightInsertSort(LineListR[],intn){inti,j;LineListtemp;for(i=1;in;i++)//从第二个开始{temp=R[i];j=i-1;//j从第一个开始比较while(j=0&&temp.keyR[j].key){//元素后移让位给tempR[j+1]=R[j];j--;//恢复前一个位置}R[j+1]=temp;//在j+1位置插入temp}}/*快速排序，升序*/voidQuickSort(LineListR[],ints,intt){//对R[s]至R[t]的元素进行快速排序inti=s,j=t;LineListtemp;if(st)//区间内至少存在一个元素的情况{temp=R[s];//用区间的第1个记录作为基准while(i!=j)//从区间两端交替向中间扫描,直至i=j为止{while(ji&&R[j].keytemp.key){//从右向左扫描,找第1个关键字小于temp.key的R[j]j--;R[i]=R[j];//找到这样的R[j],则R[i]和R[j]交换while(ij&&R[i].keytemp.key)i++;//从左向右扫描,找第1个关键字大于temp.key的R[i]R[j]=R[i];//找到这样的R[i],则R[i]和R[j]交换}R[i]=temp;QuickSort(R,s,i-1);//对左区间递归排序QuickSort(R,i+1,t);//对右区间递归排序}}}/*二分法插入排序，升序*/voidBinarySort(LineListR[],intn){intx;intl,r,m;inti,j;/*从最先的两个元素开始排序*/for(i=1;in;i++){x=R[i].key;l=1;/*下限*/r=i-1;/*上限*/while(l=r){/*中间位置*/m=(l+r)/2;if(xR[m].key)r=m-1;/*上限下移*/elsel=m+1;/*下限上移*/}/*插入元素*/for(j=i-1;j=l;j--)R[j+1]=R[j];R[l].key=x;}}/*直接选择排序，升序*/voidSelectSort(LineListR[],intn){inti,j,k;LineListtmp;for(i=0;in-1;i++){k=i;for(j=i+1;jn;j++)if(R[j].keyR[k].key)k=j;//用k指出每趟在无序区段的最小元素tmp=R[i];//将R[k]与R[i]交换R[i]=R[k];R[k]=tmp;}}/*希尔排序，升序*/voidShellSort(LineListR[],intn){inti,j,gap;LineListtmp;gap=n/2;//增量置初值while(gap0){for(i=gap;in;i++)//对所有相隔gap位置的所有元素组进行排序{tmp=R[i];j=i-gap;while(j=0&&tmp.keyR[j].key)//对相隔gap位置的元素组进行排序{R[j+gap]=R[j];j=j-gap;//移到本组中的前一个元素}R[j+gap]=tmp;j=j-gap;}gap=gap/2;//减小增量}}intmain(){LineListR[Max];intj,a[10],temp;printf(请输入10个数:);/*输入10个整数*/for(j=0;j10;j++)scanf(%d,&a[j]);inti,n=10;for(i=0;in;i++)R[i].key=a[i];printf(\n排序前的数为:\n);for(i=0;in;i++)printf(%-5d,R[i].key);printf(\n);printf(====================================================\n);BubbleSort(R,n);printf(冒泡排序后的数为:\n);for(i=0;in;i++)printf(%-5d,R[i].key);printf(\n);StraightInsertSort(R,n);printf(直接插入排序后的数为:\n);for(i=0;in;i++)printf(%-5d,R[i].key);printf(\n);BinarySort(R,n);printf(二分插入排序后的数为：\n);for(i=0;in;i++)printf(%-5d,R[i].key);printf(\n);QuickSort(R,0,n-1);printf(快速排序后的数为:\n);for(i=0;in;i++)printf(%-5d,R[i].key);printf(\n);SelectSort(R,n);printf(直接选择排序后的数为:\n);for(i=0;in;i++)printf(%-5d,R[i].key);printf(\n);ShellSort(R,n);printf(希尔排序后的数为:\n);for(i=0;in;i++)printf(%-5d,R[i].key);printf(\n\n);return0;}