/*
时间：2012年5月19日 22:18:43
功能：归并排序
*/
# include <stdio.h>
# include <malloc.h>
void Merge(int data1[], int data2[], int s, int m, int n)
{
int i, j, k;
for (i=m+1,k=s; s<=m && i<=n; ++k)
if (data1[s] < data1[i])
data2[k] = data1[s++];
else
data2[k] = data1[i++];
for (j=s; j<=m; ++j,++k)
data2[k] = data1[j];
for (j=i; j<=n; ++j,++k)
data2[k] = data1[j];
}
void Mosrt(int data1[], int data2[], int n, int len)
{
int start_p, end_p;
start_p = 0;
while (start_p+len < n)
{
end_p = start_p + 2*len-1;
if (end_p >= n)
end_p = n-1;
Merge(data1, data2, start_p, start_p+len-1, end_p);
start_p = end_p + 1;
}
if (start_p < n)
for(; start_p<n; start_p++) data2[start_p] = data1[start_p];
}
void mergesort(int data1[], int n)
{
int length = 1, k = 0;
int * data2;
//malloc()动态分配内存，sizeof()计算数据类型的字计数，n为数组中的元素个数。
data2 = (int *)malloc(sizeof(int)*n); //int * ：将已分得的内存按int型划分
if (data2 == NULL)
return;
while (length < n)
{
if (k == 0)
Mosrt(data1, data2, n, length);
else
Mosrt(data2, data1, n, length);
length *= 2;
k = 1 - k;
}
if(k == 1)
for(k=0; k<n; ++k)
data1[k] = data2[k];
}
// 数组输出。
void OutPut(int data[], int len)
{
for (int i=0; i<len; i++)
{
printf("%d ", data[i]);
}
printf("\n\n");
}
int main(void)
{
int data[] = {5, 7, 1, 6, 44, 11, 56, 33, 45, 21};
printf("未排序前：\n");
OutPut(data, 10);
mergesort(data, 10);
printf("排序以后：\n");
OutPut(data, 10);
return 0;
}
/*
结果：
-----------------------------
未排序前：
5 7 1 6 44 11 56 33 45 21
排序以后：
1 5 6 7 11 21 33 44 45 56
Press any key to continue
-----------------------------
*/