排序算法之合并排序

合并排序属于分治算法。分治算法的思想是：把原来的问题分解成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");
}