數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序算法演示系統(tǒng)-資料下載頁
2025-08-06 09:50本頁面
【正文】 t i,j,temp,k,x=0,y=0。 for(i=(L/2)。i=1。i) //建立初始堆 { CreateHeap(i,L,amp。x,amp。y)。 } x=0。 y=0。 for(i=L1,k=1。i=1。i,k++) //將堆中根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換 { temp=R[i+1].key。 R[i+1].key=R[1].key。 R[1].key=temp。 CreateHeap(1,i,amp。x,amp。y)。 printf(\t\t第%d趟堆排序的結(jié)果為：\n\t\t,k)。 for(j=1。j=L。j++) { printf(%5d,R[j].key)。 } getchar()。 printf(\n)。 } printf(\n\t\t比較次數(shù)是：%d\t\t,x)。 printf(\n\t\t移動次數(shù)是：%d\t\t,y)。}void Heap(){ int i。 printf(\n\t\t原始數(shù)據(jù)為（按回車鍵開始排序）：\n\t\t)。 for(i=1。i=L。i++) { printf(%5d,R[i].key)。 } getchar()。 printf(\n)。 Heapsort()。 printf(\n\t\t排序最終結(jié)果是：\n\t\t)。 for(i=1。i=L。i++) { printf(%5d,R[i].key)。 } printf(\n)。} 歸并排序核心思想將有n個(gè)記錄的原始序列看作n個(gè)有序子序列，每個(gè)子序列的長度為1，然后從第一個(gè)子序列開始，把相鄰的子序列兩兩合并，得到[n/2]個(gè)長度為2或1的子序列（當(dāng)子序列個(gè)數(shù)為奇數(shù)時(shí)，最后一組合并得到的序列長度為1），把這一過程稱為一次歸并排序，對第一次歸并排序后的[n/2]個(gè)子序列采用上述方法繼續(xù)順序成對歸并，如此重復(fù)，當(dāng)最后得到的長度為n的一個(gè)子序列時(shí)，該子序列便是原始序列歸并排序后的有序序列。核心代碼void Merge(int low,int mm,int high,int *x,int *y)//兩個(gè)有序序列的合并{ int i=low,j=mm+1,p=0。 RecType *R1。 //i對第一個(gè)開始到結(jié)尾，j從第二個(gè)開始到結(jié)尾 R1=new RecType[highlow+1]。 if(!R1) { printf(內(nèi)存不足！)。 } while(i=mmamp。amp。j=high)//兩序列從起始位置開始將小的元素放入到R1中 { R1[p++]=(R[i].key=R[j].key)?R[i++]:R[j++]。 (*x)++。 (*y)++。 } while(i=mm)//第二段結(jié)束，剩余放入R1中 { R1[p++]=R[i++]。 (*y)++。 } while(j=high)//第二段剩余，剩余放入R1中 { R1[p++]=R[j++]。 (*y)++。 } for(p=0,i=low。i=high。p++,i++)//剩余元素放入R1中,賦予R { R[i]=R1[p]。 (*y)++。 }}void MergePass(int length,int *x,int *y)//一次二路歸并排序{ int i。 for(i=1。i+2*length1=L。i=i+2*length) { Merge(i,i+length1,i+2*length1,x,y)。 //函數(shù)調(diào)用 } if(i+length1L) { Merge(i,i+length1,L,x,y)。 //函數(shù)調(diào)用 }}//歸并排序void Mergesort() //二路歸并排序{ int length,k,m=0,i,x=0,y=0。 printf(\n\t\t原始數(shù)據(jù)為（按回車鍵開始排序）：\n\t\t)。 for(k=1。k=L。k++) { printf(%5d,R[k].key)。 } getchar()。 printf(\n)。 for(length=1。lengthL。length*=2) { MergePass(length,amp。x,amp。y)。 m++。 //輸出語句包括排序的結(jié)果及次數(shù) printf(\t\t第%d趟歸并排序的結(jié)果為：\n\t\t,m)。 for(k=1。k=L。k++) { printf(%5d,R[k].key)。 } getchar()。 printf(\n)。 } printf(\n\t\t排序最終結(jié)果是：\n\t\t)。 for(i=1。i=L。i++) { printf(%5d,R[i].key)。 } printf(\n)。 printf(\t\t比較次數(shù)：%d\n,x)。 printf(\t\t移動次數(shù)：%d\n,y)。}21
電大資料相關(guān)推薦
鄂ICP備17016276號-1