合并排序属于分治算法。分治算法的思想是:把原来的问题分解成n个较小规模的问题,较小规模的问题与原问题相似,之后递归的解决这n个问题,最后把n个问题合并就可以得到原来问题的解。
合并排序的思想是:假设要排序数组A,那么把数组A分成两个子数组A1和A2,排序A1和A2,之后把A1和A2合并即可把A排序。其中排序A1和A2是子问题,可以把子问题再分解、合并排序解决子问题……。直到子问题分解为数组中只有一个数字时(这时可以把一个数字看成是已经排序的),开始合并。
合并伪代码如下:
MERGE(A,p,q,r)//其中A[p……q]和A[q+1……r]都已经排序好
n1=q-p+1
n2=r-q
//创建两个数组来做临时变量存储
create arrays L[1..n1+1] and R[1..n2+1]
for i=1 to n1
do L[i]=A[p+i-1]
for j=1 to n2
do R[j]=A[q+j]
L[n1+1]=∞
R[n2+1]=∞
i=1
j=1
for k=p to r
do if L[i]<=R[j]
then A[k]=L[i]
i=i+1
else A[k]=R[j]
j=j+1
下面就用MERGE-SORT来对数组进行排序了
MERGE-SORT(A,p,r)
if p<r
then q=(p+r)/2
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE(A,p,q,r)
合并排序的时间复杂度为nlog2(n)
C++实现代码如下
#include <iostream> #include <vector> #include <iterator> using namespace std; void Merge(vector<int> &A, vector<int>::iterator p, vector<int>::iterator q, vector<int>::iterator r) { vector<int> arrayLeft(p,q+1); vector<int> arrayRight(q+1,r); int temp=1000000;//足够大,做哨兵,排序的数中不可以大于这个数 arrayLeft.push_back(temp); arrayRight.push_back(temp); vector<int>::iterator iterLeft=arrayLeft.begin(); vector<int>::iterator iterRight=arrayRight.begin(); vector<int>::iterator iterA=p; for (;iterA!=r;iterA++) { if (*iterLeft<*iterRight) { *iterA=*iterLeft; iterLeft++; } else { *iterA=*iterRight; iterRight++; } } for (int i=0;i<5;i++) { cout<<A[i]; } cout<<endl; return; } void Merge_Sort(vector<int>&A, vector<int>::iterator p, vector<int>::iterator r) { if (p<r-1) { vector<int>::difference_type halfLength=(r-p-1)/2; vector<int>::iterator q=p+halfLength; Merge_Sort(A,p,q+1); Merge_Sort(A,q+1,r); Merge(A,p,q,r); } return; } int main() { int array[5]={4,5,2,3,1}; vector<int> A(array,array+5); Merge_Sort(A,A.begin(),A.end()); for (int i=0;i<5;i++) { cout<<A[i]; } system("pause"); }