归并排序

arr[]存储所有待排关键字的数组，low到high的关键字为一个子表，从mid+1到high为另一个关键字的子表。所以可以看出，归并排序可以对一个序列中任意一部分的元素进行排序，通过指定范围low-high就行。int n1=mid-low+1;显然n1为low到high范围里的关键字的个数。int n2=high-mid;显然n2是mid+1到high的关键字的个数。

guibingpaixu 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void merge(int arr[],int low,int mid,int high)
{
	int i,j,k;
	int n1=mid-low+1;
	int n2=high-mid;
	int L[n1],R[n2];
	for(i=0;i<n1;i++)
		L[i]=arr[low+i]; //将arr[]中的low到mid的元素赋给L[]中
	for(j=0;j<n2;j++)
		R[j]=arr[mid+1+j]; //将arr[]中的mid+1到high的元素赋给R[]中
	i=0; 
	j=0;
	k=low;
	while(i<n1&&j<n2)  
	{
		if(L[i]<=R[j])   //L数组和R数组中相对应的元素进行大小比较
			arr[k]=L[i++]; //此时L数组的元素较小，赋给arr数组中，且i加一
		else
			arr[k]=R[j++]; // R数组中的元素较小
		k++; //k指向arr数组中的元素，被赋过值了，所以加一
	}
	while(i<n1)  //L数组中若是比较完之后有剩余就将他加到arr数组的后面
		arr[k++]=L[i++];
	while(j<n2)  //同理是R数组中若有剩余
		arr[k++]=R[j++];
}

void mergeSort(int arr[],int low,int high)
{
	if(low<high)
	{
		int mid=(low+high)/2; //计算出中间位置
		mergeSort(arr,low,mid); 
		mergeSort(arr,mid+1,high);
		merge(arr,low,mid,high);
	}
}