排序算法习题

排序算法分析与填空一、插入排序算法1.1直接插入排序算法：---稳定性voidInsertSort(intR[],intn){inti,j,tmp;for(i=1;i<n;i++){tmp=R[i];j=①_________________;while(②________________&&j>=0){③_________________;j--;} R[④__________________________]=tmp;}}直接插入排序算法参考答案：i-1②R[j]>tmp③R[j+1]=R[j]④j+11.2希尔排序算法：---不稳定性voidShellSort(intR[],intn){ inti,j,gap; inttmp; gap=n/2; while(gap>0) { for(i=gap;i<n;i++){ tmp=R[i]; j=①___________________; while(j>=0&&R[j]>tmp){R[②____________]=R[j];j=j-gap;}③_____________=tmp; }④___________________; }}希尔排序算法参考答案：i-gap②j+gap③R[j+gap]④gap=gap/2二、交换排序算法2.1冒泡排序算法---稳定性改进的冒泡排序法？voidBubbleSort(intR[],intn){inti,j,tmp;for(i=0;①_______________;i++)for(j=n-1;②______________;j--)if(③________________){tmp=R[j-1];R[j-1]=R[j];R[j]=tmp;}}冒泡排序算法参考答案：①i<n-1②j>i③R[j-1]>R[j]2.2快速排序法---不稳定性更换指标的快速排序算法：voidQuickSort(intR[],ints,intt){voidQuickSort(intR[],ints,intt){ inti=s,j=t,tmp,pivot;/*中心*/ pivot=R[(s+t)/2]; if(s<t) { while(i<j) {while(j>i&&R[j]>pivot)j--; while(i<j&&R[i]<pivot)i++; if(R[i]==pivot&&R[j]==pivot)j--; if(i<j) {tmp=R[i]; R[i]=R[j]; R[j]=tmp; } QuickSort(R,s,i-1); QuickSort(R,i+1,t); } }{ inti=s,j=t,tmp; if(①______________) {tmp=R[s]; while(②_______________) {while(j>i&&R[j]>tmp)j--; R[i]=R[j]; while(i<j&&R[i]<=tmp)i++; R[j]=R[i]; }③________________; QuickSort(R,s,i-1);④___________________________________; }}快速排序算法参考答案：s<t②i<j或者i！=j③R[i]=tmp④QuickSort(R,i+1,t)三、选择排序算法3.1直接选择排序算法-----不稳定性voidSelectSort(intR[],intn){ inti,j,tmp,k; for(i=0;①______________;i++) {k=i; for(②______________;j<n;j++) if(R[k]>R[j])③_____________________________________; if(④______________________________) {tmp=R[k]; R[k]=R[i]; R[i]=tmp; } }}①i<n-1②j=i+1③k=j④k!=i3.2堆排序算法-----不稳定性/*建堆算法：*/voidsift(intR[],intlow,inthigh){inti=low,j=2*i,tmp;tmp=R[i];while(j<=high){ if(j<high&&R[j]<R[j+1])①_______________;/*如果右孩子大，把j指向右孩子*/ if(tmp<R[j]) {R[i]=R[j]; i=j;②__________________; } elsebreak;}R[i]=③_________________;/*被筛选的结点放入最终位置*/}/*堆排序算法：*/voidHeapSort(intR[],intn){ inti,tmp; for(i=n/2;i>=1;i--)④_____________________;for(i=n;⑤_____________;i--){tmp=R[1];R[1]=R[i];R[i]=tmp;⑥___________________;}}建堆及堆排序算法参考答案;j++②j=2*i③tmp④sift(R,i,n)⑤i>=2⑥sift(R,1,i-1)三、归并排序算法----稳定性Merge()、MergePass()MergeSort()算法填空：先是表长1的合并，然后是表长为2的合并，然后是表长为4的合并，依次类推….这是自底向上的算法voidMerge(intR[],intlow,intmid,inthigh){ intR1[N]; inti=low,j=mid+1,k=0; while(i<=mid&&j<=high) { if(R[i]<=R[j]){①________;②_________;③___________;} else{R1[k]=R[j];j++;k++;}}while(④______________){R1[k]=R[i];i++;k++;}while(j<=high){R1[k]=R[j];j++;k++;} for(k=0,i=low;i<=high;i++;k++) R[i]=R1[k];}voidMergePass(intR[],intlength,intn){ inti; for(i=0;i+2*length-1<n;i=i+2*length) Merge(R,i,⑤___________,i+2*length-1);if(⑥_______________)Merge(R,i,i+length-1,n-1);/*剩下的两个子表，后者长度小于length*/}voidMergeSort(intR[],intn){intlength; for(length=1;length<n;⑦_______________)/*进行log2n趟归并*/ MergePass(R,length,n);}参考答案：①R1[k]=R[i]②i++③k++④i<=mid⑤i+length-1⑥i+length-1<n⑦length=2*length上述的自底向上的归并算法虽然效率较高，但其可读性很差。若采用自顶向下的方法设计，算法更简洁。设归并排序的当前区间是R[low..high],则递归归并两个步骤如下：分解:当前区间R[low..high]一分为二，即求mod=(low+high)/2;递归的对两个子区间R[low..mid]和R[mid+1..high]进行继续分解。其终结条件是子区间长度为(因为一个记录的子表一定是有序的)归并：与分解过程相反，将已排序的两个子区间R[low..mid]R[mid+1..high]归并为一个有序的区间R[low..high]对应的算法如下：voidMergeSortDC(intR[],intlow,inthigh){ intmid; mid=(low+high)/2; if(①_____________) { MergeSortDC(R,low,mid);②__________________；③__________________; }}voidMergeSort1(intR[],intn){ MergeSortDC(R,0,n-1);}参考答案：①low<high②MergeSortDC(R,mid+1,high)③Merge(R,low,mid,high)四、基数排序----稳定性基数排序算法的填空：#include"stdio.h"#include"stdlib.h"intmain(){ intdata[10]={73,22,93,43,55,14,28,65,39,81}; inttemp[10][10]={0}; intorder[10]={0}; inti,j,k,n,lsd; k=0;n=1; while(n<=10){for(i=0;i<10;i++) { lsd=①________________; temp[lsd][order[lsd]]=data[i]; order[lsd]++; } printf("\n重新排列"); for(i=0;i<10;i++) {if(②___________________) for(j=0;j<order[i];j++) { data[k]=③_______