归并排序


		按照分治三步法，对归并排序算法介绍如下：
（1）划分问题：把序列分成元素个数尽量相等的两半；
（2）递归问题：把两半元素分别排序；
（3）合并问题：把两个有序表合并成一个。
前两部分很容易完成的，关键在于如何把两个有序表合并成一个。图8-2演示了一个合并的过程。每次只需要把两个序列的最小元素加以比较，删除其中的较小元素并加入合并后的新表即可。由于需要一个新表来存放结果，所以附加空间n。

归并排序的代码如下：
程序8-4  归并排序（从小到大）
[cpp]  
void merge_sort(int* A, int x, int y, int* T) {  
  if(y-x > 1){  
    int m = x + (y-x)/2;          //划分  
    int p = x, q = m, i = x;  
    merge_sort(A, x, m, T);        //递归求解  
    merge_sort(A, m, y, T);        //递归求解  
    while(p < m || q < y) {  
      if(q >= y || (p < m && A[p] <= A[q]))   //从左半数组复制到临时空间  
        T[i++] = A[p++];  
      else                                    //从右半数组复制到临时空间  
        T[i++] = A[q++];  
    }  
    for(i = x; i < y; i++) A[i]= T[i];       //从辅助空间复制到A数组  
  }  
}  
 
 
代码中的两个条件是关键。首先，只要有一个序列非空，就要继续合并（while(p<m||q<
y)）,所以正确的方式是：
    （1）如果第二个序列为空（此时第一个序列一定非空），复制A[p]。
（2）否则（第二个序列非空），当且仅当第一个序列也非空，且A[p]≤A[q]时，才复制A[p]。
[cpp] 
#include<iostream>  
#include<string.h>  
#include<stdio.h>  
#include<ctype.h>  
#include<algorithm>  
#include<stack>  
#include<queue>  
#include<set>  
#include<math.h>  
#include<vector>  
#include<map>  
#include<deque>  
#include<list>  
using namespace std;  
void merge_sort(int* a, int start, int end, int* b)  
{  
    if(end-start>1)//确定起始位置——>递归的出口  
    {  
        int mid=start+(end-start)/2;           //划分  
        int p=start, q=mid;  
        int w=start;  
        merge_sort(a,start,mid,b);        //递归求解  
        merge_sort(a,mid,end,b);        //递归求解  
        while(p<mid||q<end)  
        {  
            if((p<mid&&a[p]<=a[q])||q>=end)   //从左半数组复制到临时空间  
                b[w++]=a[p++];  
            else                                    //从右半数组复制到临时空间  
                b[w++]=a[q++];  
        }  
        for(int i=start; i<end; i++)  
            a[i]=b[i];       //从辅助空间复制到a数组  
    }  
}  
int main()  
{  
    int a[333],b[333];  
    int n;  
    while(scanf("%d",&n)!=EOF)  
    {  
        for(int i=0; i<n; i++)  
            scanf("%d",&a[i]);  
        merge_sort(a,0,n, b);  
        for(int i=0; i<n-1; i++)  
            printf("%d ",a[i]);  
        printf("%d\n",a[n-1]);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,