排序算法習(xí)題

排序算法分析與填空一、插入排序算法1.1直接插入排序算法：---穩(wěn)定性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希爾排序算法：---不穩(wěn)定性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冒泡排序算法---穩(wěn)定性改進(jìn)的冒泡排序法？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快速排序法---不穩(wěn)定性更換指標(biāo)的快速排序算法：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直接選擇排序算法-----不穩(wěn)定性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堆排序算法-----不穩(wěn)定性/*建堆算法：*/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]=③_________________;/*被篩選的結(jié)點放入最終位置*/}/*堆排序算法：*/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)三、歸并排序算法----穩(wěn)定性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;⑦_(dá)______________)/*進(jìn)行l(wèi)og2n趟歸并*/ MergePass(R,length,n);}參考答案：①R1[k]=R[i]②i++③k++④i<=mid⑤i+length-1⑥i+length-1<n⑦length=2*length上述的自底向上的歸并算法雖然效率較高，但其可讀性很差。若采用自頂向下的方法設(shè)計，算法更簡潔。設(shè)歸并排序的當(dāng)前區(qū)間是R[low..high],則遞歸歸并兩個步驟如下：分解:當(dāng)前區(qū)間R[low..high]一分為二，即求mod=(low+high)/2;遞歸的對兩個子區(qū)間R[low..mid]和R[mid+1..high]進(jìn)行繼續(xù)分解。其終結(jié)條件是子區(qū)間長度為(因為一個記錄的子表一定是有序的)歸并：與分解過程相反，將已排序的兩個子區(qū)間R[low..mid]R[mid+1..high]歸并為一個有序的區(qū)間R[low..high]對應(yīng)的算法如下：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)四、基數(shù)排序----穩(wěn)定性基數(shù)排序算法的填空：#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]=③_______