歸並排序就是利用歸並的思想實現的排序方式。他的原理是假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度是1，然後兩兩合並，得到[n/2][x]表示不小於x的最小整數）個長度為2或1的有序子序列；再兩兩歸並，......，如此重復，直至得到一個長度為n的有序序列為止，這種排序方法稱為2路歸並排序。
#include <stdio.h>
#include <stdlib.h>
void swap(int arr[] ,int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void Merge(int sr[], int tr[], int i, int m, int n)
{
int j;
int k;
int l;
for(j=m+1,k=i; i<=m && j<=n; k++)
{
if(sr[i]<sr[j])
tr[k]=sr[i++];
else
tr[k]=sr[j++];
}
if(i<=m)
{
for(l=0; l<=m-i; l++)
tr[k+l]=sr[i+l];
}
if(j<=n)
{
for(l=0; l<n-j; l++)
tr[k+l]=sr[j+l];
}
}
void MergeSort(int arr[], int arr1[],int s, int t)
{
int m;
int arr2[10];
if(s==t) //s=0 t=0; //待排序長度為1
arr1[s]=arr[s];
else
{
m = (s+t)/2;
MergeSort(arr, arr2, s, m);
MergeSort(arr, arr2, m+1, t);
Merge(arr2,arr1,s,m,t);
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int arr1[9];
printf("排序前：\n");
print(arr, n);
MergeSort(arr, arr1,0,n-1);
printf("排序後：\n");
print(arr1, n);
system("pause");
return 0;
}
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282290
