前言：

　　在今后的日子里，我將持續(xù)更新博客，討論《算法導(dǎo)論》一書中的提到的各算法的C++實現(xiàn)。初來乍到，請多指教。

今日主題：　　

　　今天討論《算法導(dǎo)論》第二章算法基礎(chǔ)中的歸并排序算法。下面是該算法的代碼Merge.h：

　　

#include <stdlib.h>namespace dksl {/** 歸并* numArray為整形數(shù)組* head為要歸并的數(shù)組的開始位置索引* waist為要歸并的數(shù)組的中間位置索引* tail-1為要歸并的數(shù)組的結(jié)束位置索引*/void merge(int *numArray,const int head,const int waist,const int tail){int begin=head,start=waist,index=0;int length=tail-head;int* temp=new int[length]; if(temp==nullptr)throw "系統(tǒng)為程序分配內(nèi)存失敗";while(begin<waist&&start<tail){if(numArray[begin]<numArray[start])temp[index++]=numArray[begin++];elsetemp[index++]=numArray[start++];}if(begin==waist){while(start<tail)temp[index++]=numArray[start++];}else if(start==tail){while(begin<waist)temp[index++]=numArray[begin++];}//memcpy(numArray+head, temp, sizeof(int)*length);int i=0;for(i,index=head;i<length;i++,index++){numArray[index]=temp[i];}delete(temp);}void sort(int *numArray,const int head,const int tail){ int length = tail - head; int begin = head, middle = ((head+tail)%2 == 0) ? (head+tail)/2 : (head+tail+1)/2, end = tail; if(length < 2) return; else if(length == 2) merge(numArray,begin,middle,end); else { if( middle- begin > 1) sort(numArray,begin,middle); if( end- middle > 1) sort(numArray,middle,end); merge(numArray,begin,middle,end); }} }

?　　c++動態(tài)數(shù)組分配很方便，“int* temp=new int[length]; ”length在程序運行過程中確定。為了養(yǎng)成良好的習(xí)慣，請在定義的指針空間使用完后，將其刪除。

　　下面是本算法的測試代碼MergeSort.cpp：

#include "stdafx.h" #include <iostream> #include "Merge.h"using namespace std; using namespace dksl; int _tmain(int argc, _TCHAR* argv[]) {int a[10] = {1, 4, 8, 5, 10, 25, 54, 15, 12, 2}; int i = 0; sort(a, 0, 10); cout<<"The sorted array is:"; for(i = 0; i < 10; i++) cout<<a[i]<<" "; cout<<endl;system("PAUSE");return 0; }

?　　運行結(jié)果：

轉(zhuǎn)載于:https://www.cnblogs.com/DKSL/p/3145122.html

總結(jié)

以上是生活随笔為你收集整理的《算法导论》——MergeSort的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。