merge_sort.cpp

merge_sort的一个示例程序,希望能对初学者有所帮助

//merge_sort by suqiang @ neuq & jlu 更详细的内容请访问：http://blog.csdn.net/china8848
#include <iostream>
using namespace std;
//定义数组中的最大值
#define MAX_NUM 1000
//定义数组元素个数
#define MAX_SIZE 1000
//pa是指向A数组的指针，p,q,r为数组下标
//假设A[p..q],A[q+1..r]已经排好序，返回A[p..r]已经排好序的A 
//思路是将A[p..q],A[q+1..r]分别赋值给数组A1，A2，并将最后一个元素设为最大值，作为哨兵
//然后用两个指针i，j从小到大赋值到A
void merge(int *pa,int p,int q,int r)
{
    int n1,n2,i,j,k;
    n1=q-p+1;
    n2=r-q;
    
    //p1,p2分别为指向A1，A2的指针
    int *p1,*p2;
    p1=new int[n1+1];
    p2=new int[n2+1];
    //将A[p..q],A[q+1..r]分别赋值给数组A1，A2
    for(i=0;i<n1;i++)
        *(p1+i)=*(pa+p+i);
    for(i=0;i<r-q;i++)
        *(p2+i)=*(pa+q+i+1);
    //将最后一个元素设为最大值，作为哨兵
    *(p1+n1)=MAX_NUM;
    *(p2+n2)=MAX_NUM;

    //用指针i，j从小到大赋值到A
    i=0;j=0;
    for(k=p;k<=r;k++)
    {
        if(*(p1+i)>=*(p2+j))
        {
            *(pa+k)=*(p2+j);
            j++;
        }
        else
        {
            *(pa+k)=*(p1+i);
            i++;
        }
    }
    free(p1);
    free(p2);
}
//合并排序，pa为指向数组A的指针，p，r为下标，对A[p..r]进行合并排序
void merge_sort(int *pa,int p,int r)
{
    if(p<r)
    {
        int q=(p+r)/2;
        merge_sort(pa,p,q);
        merge_sort(pa,q+1,r);
        merge(pa,p,q,r);
    }
}

int main()
{
    int A[MAX_SIZE],i;
    for(i=0;i<10;i++)
        A[i]=10-i;
    int *pa=A;
    merge_sort(pa,0,9);
    for(i=0;i<10;i++)
        cout<<A[i]<<endl;
    return 1;
}