數(shù)據(jù)結(jié)構(gòu)課程設(shè)報(bào)告—各種排序算法的比較-文庫(kù)吧
2025-07-06 12:23 本頁(yè)面
【正文】 經(jīng)排好序 for(int j=0。jcurrentsizei。j++) if(arr[j]arr[j+1])//逆序 { swap(arr[j],arr[j+1])。//相鄰元素交換位置 finish=0。 }//排序結(jié)束標(biāo)志置為,表示本趟發(fā)生了交換，說(shuō)明還沒(méi)有排好序 i++。 cout第++num趟排序結(jié)果為:。 for(int t=0。tcurrentsize。t++) coutarr[t] 。 coutendl。 } num=0。} e 簡(jiǎn)單選擇排序 template class typevoid sortlisttype::selectsort()//簡(jiǎn)單選擇排序{ int k。 for(int i=0。i=currentsize1。i++) { k=i。 for(int j=i+1。jcurrentsize。j++) if(arr[j]arr[k]) k=j。//k 指示當(dāng)前序列中最小者的位置 if(k!=i)//最小關(guān)鍵字的數(shù)據(jù)元素位置不等于i swap(arr[i],arr[k])。 cout第++num趟排序結(jié)果為:。 for(int t=0。tcurrentsize。t++) coutarr[t] 。 coutendl。 } num=0。} f 快速排序：template class type//快速排序void sortlisttype::quicksort(int low,int high)//在待排序區(qū)間[low,high]上，遞歸地進(jìn)行快速排序{ int i=low,j=high。 type temp=arr[low]。//取區(qū)間第一個(gè)位置為基準(zhǔn)位置 if(ij) { while(ij) { while(ijamp。amp。temparr[j])j。 if(ij){swap(arr[i],arr[j])。i++。} while(ijamp。amp。temp=arr[i])i++。 if(ij){swap(arr[i],arr[j])。j。} } arr[i]=temp。//將基準(zhǔn)元素就位 cout第++x趟排序結(jié)果為:。 for(int t=0。tcurrentsize。t++) coutarr[t] 。 coutendl。 quicksort(low,i1)。//在左子區(qū)間遞歸進(jìn)行快速排序 quicksort(i+1,high)。//在右子區(qū)間遞歸進(jìn)行快速排序 } } g 堆排序 (1)建立最大堆的偽代碼如下：template class type//建立最大堆void sortlisttype::filterdown(const int start){//向下調(diào)整使從start開始到currentsize1為止的子表成為最大堆 int i=start,j=2*i+1。//j為i的左孩子 int tablesize=currentsize。 type temp=arr[i]。 while(j=currentsize1) { if(jcurrentsize1 amp。amp。 arr[j]arr[j+1]) j++。//在兩個(gè)孩子中選關(guān)鍵字較大者 if(temp=arr[j])break。 else{arr[i]=arr[j]。i=j。j=2*j+1。 } } arr[i]=temp。}(2)堆排序template class type//堆排序void sortlisttype::heapsort(){ int tablesize=currentsize。 for(int i=(currentsize2)/2。i=0。i) filterdown(i)。 //初始建堆 for(int i=currentsize1。i=1。i) { swap(arr[0],arr[i])。//堆頂元素和最后一個(gè)元素交換 currentsize。 filterdown(0)。//重建最大堆 cout第++num趟排序結(jié)果為:。 for(int t=0。ttablesize。t++) coutarr[t] 。 coutendl。 } num=0。 currentsize=tablesize。}h 歸并排序歸并算法：template class typevoid sortlisttype::merge(sortlisttypeamp。sourcetable,sortlisttypeamp。mergedtable,const int left,const int mid,const int right){ int i=left,j=mid+1,k=left。//指針初始化//i是前一段的當(dāng)前元素位置，j是后一段的當(dāng)前元素位置，k是輔助數(shù)組的當(dāng)前位置 while(i=midamp。amp。j=right) if([i]=[j]) {[k]=[i]。i++。k++。} else{[k]=[j]。j++。k++。} if(i=mid) for(int p=k,q=i。q=mid。p++,q++) [p]=[q]。//把前一段復(fù)制到mergedtable else for(int p=k,q=j。q=right。p++,q++) [p]=[q]。//把后一段復(fù)制到mergedtable}一趟歸并算法template class typetemplate class typevoid sortlisttype::mergepass(sortlisttypeamp。sourcetable,sortlisttypeamp。mergedtable,const int len){ int i=0。 while(i+2*len=currentsize1)//表示至少有個(gè)子序列 { merge(sourcetable,mergedtable,i,i+len1,i+2*len1)。 i+=2*len。 } if(i+len=currentsize1)//若只有最后兩個(gè)子序列 merge(sourcetable,mergedtable,i,i+len1,currentsize1)。 else//若只有最后一個(gè)子序列 for(int j=i。j=currentsize1。j++) [j]=[j]。 if(len=currentsize1) {if(numcurrentsize) { cout第++num趟排序結(jié)果為:。 for(int t=0。tcurrentsize。t++) cout[t] 。 coutendl。 } }}歸并排序：template class typevoid sortlisttype::mergesort(sortlisttype amp。table ){//按數(shù)據(jù)元素關(guān)鍵字非遞減的順序?qū)ε判虮韙able中數(shù)據(jù)元素進(jìn)行遞歸排序 sortlisttype temptable。 int len=1。 while(lencurrentsiz
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1