归并排序
按照分治三步法，对归并排序算法介绍如下：
（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++ ,
