归并排序

* author : Deng yong
* date:2016 2 24
* filename : 归并排序
*/
#include <iostream>
template<typename T>

void merget( T A[], int p, int q, int r)
{
int n_1=q-p+1; //已经排序好的数组p->q的长度
int n_2=r-q; //已经排序好的数组q->r的长度

T L[n_1];//p->q
T R[n_2];//q+1->r

std::cout<<"L"<<std::endl;

for ( int i=0; i<n_1;i++)
{
L[i]=A[p+i];
std::cout<<L[i]<<" ";
}
//test
std::cout<<std::endl;

std::cout<<"R"<<std::endl;
for ( int i=0; i<n_2;i++)
{
R[i]=A[q+i+1];
std::cout<<R[i]<<" ";
}
int i=0;
int j=0;
int k=p;
std::cout<<std::endl;

std::cout<<"start"<<std::endl;

while (i<n_1&&j<n_2)

{

if (L[i]<R[j])
{
A[k]=L[i];
i++;
}
else
{

A[k]=R[j];
j++;
}

std::cout<<"A"<<k<<"**"<<A[k]<<std::endl;
k++;
}




while (i<n_1)
{
A[k++]=L[i++];
}
while (j<n_2)
{
A[k++]=R[j++];
}



}

#include <iostream>

template <typename T>

void merge_sort(T A[], int p, int r)
{
if (p<r)
{
int q=(p+r)/2;
merge_sort( A, p,q);
merge_sort(A,q+1,r);
merget(A,p,q,r);
}
}

int main()
{
#ifdef test_merget
int a[6]={0,5,7,2,4,8};
merget(a,0,2,5);
for (int i=0;i<6;i++)
{
std::cout<<a[i]<<std::endl;
}
#else
int a[6]={0,6,2,9,4,5};

merge_sort(a,0,5);
for ( int i=0;i<6;i++)
{
std::cout<<a[i]<<std::endl;
}

#endif

}

归并排序

原文：http://www.cnblogs.com/caffe/p/5215114.html