归并排序(merge sort)体现了分治的思想，即将一个待排序数组分为两部分，对这两个部分进行归并排序，排序后，再对两个已经排序好的数组进行合并。这种思想可以用递归方式很容易实现。归并排序的时间复杂度为
O(nlogn)，空间复杂度为
O(n)。
实现代码如下：
#include < stdio.h >
#include " common.h "
void merge( int data[], int p, int q, int r)
{
int i, j, k, n1, n2;
n1 = q - p + 1 ;
n2 = r - q;
int L[n1];
int R[n2];
for (i = 0 , k = p; i < n1; i ++ , k ++ )
L[i] = data[k];
for (i = 0 , k = q + 1 ; i < n2; i ++ , k ++ )
R[i] = data[k];
for (k = p, i = 0 , j = 0 ; i < n1 && j < n2; k ++ )
{
if (L[i] > R[j])
{
data[k] = L[i];
i ++ ;
}
else
{
data[k] = R[j];
j ++ ;
}
}
if (i < n1)
{
for (j = i; j < n1; j ++ , k ++ )
data[k] = L[j];
}
if (j < n2)
{
for (i = j; i < n2; i ++ , k ++ )
data[k] = R[i];
}
}
void merge_sort( int data[], int p, int r)
{
if (p < r)
{
int q = (p + r) / 2 ;
merge_sort(data, p, q);
merge_sort(data, q + 1 , r);
merge(data, p, q, r);
}
}
void test_merge_sort()
{
int data[] = { 44 , 12 , 145 , - 123 , - 1 , 0 , 121 };
printf( " -------------------------------merge sort----------------------------/n " );
out_int_array(data, 7 );
merge_sort(data, 0 , 6 );
out_int_array(data, 7 );
}
int main()
{
test_merge_sort();
return 0 ;
}
国内最棒的Google Android技术社区（eoeandroid），欢迎访问！
《银河系列原创教程》发布
《Java Web开发速学宝典》出版，欢迎定购
实现代码如下：
#include < stdio.h >
#include " common.h "
void merge( int data[], int p, int q, int r)
{
int i, j, k, n1, n2;
n1 = q - p + 1 ;
n2 = r - q;
int L[n1];
int R[n2];
for (i = 0 , k = p; i < n1; i ++ , k ++ )
L[i] = data[k];
for (i = 0 , k = q + 1 ; i < n2; i ++ , k ++ )
R[i] = data[k];
for (k = p, i = 0 , j = 0 ; i < n1 && j < n2; k ++ )
{
if (L[i] > R[j])
{
data[k] = L[i];
i ++ ;
}
else
{
data[k] = R[j];
j ++ ;
}
}
if (i < n1)
{
for (j = i; j < n1; j ++ , k ++ )
data[k] = L[j];
}
if (j < n2)
{
for (i = j; i < n2; i ++ , k ++ )
data[k] = R[i];
}
}
void merge_sort( int data[], int p, int r)
{
if (p < r)
{
int q = (p + r) / 2 ;
merge_sort(data, p, q);
merge_sort(data, q + 1 , r);
merge(data, p, q, r);
}
}
void test_merge_sort()
{
int data[] = { 44 , 12 , 145 , - 123 , - 1 , 0 , 121 };
printf( " -------------------------------merge sort----------------------------/n " );
out_int_array(data, 7 );
merge_sort(data, 0 , 6 );
out_int_array(data, 7 );
}
int main()
{
test_merge_sort();
return 0 ;
}
国内最棒的Google Android技术社区（eoeandroid），欢迎访问！
《银河系列原创教程》发布
《Java Web开发速学宝典》出版，欢迎定购
