數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序綜合-在線瀏覽
2025-03-05 14:19本頁面
【正文】 是交換B[j],B[j+1], Swap(B[j],B[j+1])。移動次數(shù)c[2]加3。比較次數(shù)a[2]加1如果沒有交換元素，則last=0,退出循環(huán)i=last。判斷l(xiāng)eftright 是調(diào)用QSort(left,right)，開始一趟快速排序，Q[left]作為分割元素，并且j=QSort(left,right)； 否遞歸調(diào)用函數(shù)QuickSort(left,j1)， 對低端序列快速排序遞歸調(diào)用函數(shù)QuickSort(j+1,right)， 對高端序列快速排序結(jié)束 流程圖5開始(5) :合并排序: 判斷sizen 是初始化left=0。 判斷right1+sizen1 否 right2=right1+size。 是 否遞歸調(diào)用Merge(left,right1,right2)，合并相鄰的兩個子序列；left=right2+1， 確定下次合并的子序列的下界元素個數(shù)擴大一倍，size*=2結(jié)束流程圖6 源程序includeiostreaminclude includefstreamincludeincludeincludeiomanip//包含列表的函數(shù)using namespace std。//a[],b[],c[]分別記錄比較次數(shù)，交換次數(shù)，移動次數(shù)ifstream outfile。 void InsertSort()。 void BubbleSort()。 void MergeSort()。 int QSort(int left,int right)。 int *I,*S,*Q,*B,*M。}。scanf(%d,amp。I=new int[n]。Q=new int[n]。M=new int[n]。in。//將隨機生成的資料寫入文件ofstream infile。//將對象與文件關(guān)聯(lián)for(i=0。i++){double w=I[i]。 }()。a,intamp。a=b。}void SortableSList::InsertSort()//直接插入排序{ for(int i=1。i++) { int j=i。//將待插入元素存入temp c[0]++。amp。 I[j]=I[j1]。 c[0]++。 I[j]=temp。for(int i=0。i++){ s=i。jn。 if(S[j]S[s]) s=j。//最小元素與待排序序列的第一個交換 c[1]=c[1]+3,b[1]++。 //以初始序列為待排序序列開始快速排序}int SortableSList::QSort(int left,int right){int i=left,j=right+1。 a[3]++。 do { j。 }while(Q[j]Q[left])。}while(ij)。 //交換分割元素Q[left]和Q[j]的位置c[3]=c[3]+3,b[3]++。}void SortableSList::QuickSort(int left,int right){if(leftright){ int j=QSort(left,right)。 //對低端序列快速排序 QuickSort(j+1,right)。 i=n1。 //進(jìn)入循環(huán)就將last置為0 for(j=0。j++)//從上往下進(jìn)行比較 { if(B[j+1]B[j]) { Swap(B[j],B[j+1])。 b[2]++。 } a[2]++。 //如果沒有交換元素，則last=0,退出循環(huán) }}//兩路合并排序void SortableSList::Merge(int left,int right1,int right2)//兩路合并{//right1,right2分別為兩個子序列的上界int*temp=new int[right2left+1]。 //i,j是兩個子序列的游動指針，k是temp的游動指針while((i=right1)amp。(j=right2))//若兩個子序都不空，則循環(huán){ a[4]++。 else temp[k++]=M[j++],c[4]++,b[4]++。while(j=right2) //若第二個子序列還有剩余的就存入temp temp[k++]=M[j++],c[4]++,b[4]++。k=right2。}void SortableSList::MergeSort()//合并排序{int left,right2,right1。 //初始化子序列中元素的個數(shù)為1while(sizen){ left=0。 //確定子序列1的下界 if(right1+sizen1) right2=n1。 Merge(left,right1,right2)。 //確定下次合并的子序列的下界 } size*=2。getchar()。printf( ***************************尊敬的用戶您好*************************** \n)。printf( ****歡迎使用由計科1班 喻思遠(yuǎn) 20
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1