归并排序（Merge Sort）

时间：2014-03-28 12:10:09 收藏：0 阅读：309

算法描述

归并操作的过程如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

示例代码

#include<iostream>
 
using 
namespace std;
 
int data[8]={1,2,3,4,1,9,6,8};
 
int merge(int 
unSorted[],int 
sorted[],int 
first,int 
mid,int 
last){
    int 
fpoint=first;
    int 
spoint=mid+1;
    int 
sortedPoint=first;
    while(fpoint<=mid && spoint<=last){
        if(unSorted[fpoint]<unSorted[spoint])
            sorted[sortedPoint++]=unSorted[fpoint++];
        else
            sorted[sortedPoint++]=unSorted[spoint++];
    }
    if(fpoint>mid)
        while(sortedPoint<=last)
            sorted[sortedPoint++]=unSorted[spoint++];
    if(spoint>last)
        while(sortedPoint<=last)
            sorted[sortedPoint++]=unSorted[fpoint++];
    for(int 
i=first;i<=last;i++)
        unSorted[i]=sorted[i];
    return 
0;
}
int 
myMergeSort(int 
unSorted[],int 
sorted[],int 
begin,int 
end){
    if(begin<end){
        int 
mid=(begin+end)/2;
        myMergeSort(unSorted,sorted,begin,mid);
        myMergeSort(unSorted,sorted,mid+1,end);
        merge(unSorted,sorted,begin,mid,end);
    }
 
 
     
    return 
0;
}
 
int 
main(){
    int 
*sortedData=(int 
*)malloc(sizeof(data));
    //merge(data,sortedData,0,3,7);
    myMergeSort(data,sortedData,0,7);
    for(int 
i=0;i<8;i++)
        cout<<sortedData[i]<<" ";
    getchar();
    return 
0;
 
}

归并排序（Merge Sort）,布布扣,bubuko.com

原文：http://www.cnblogs.com/seair/p/3629304.html