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