用C语言实现归并算法，以下是代码，归并的函数测试过，可用，但调用递归排序后没效果。

Question

程序中如果有代码风格问题或者类似指针没free的问题都欢迎指出
#include <stdio.h>
#include <malloc.h>
int *merger(int *arr1, int length1, int *arr2, int length2);
void sort(int *arr, int length);
int main(void)
{
int i;
/* 测试merger的归并效果
int a[] = {3, 1, 5, 7, 9};
int b[] = {2, 6, 4, 8};
int *p = NULL;
p = merger(b, 4, a, 5); */
int p[] = {1, 3, 5, 7, 9, 8, 6, 4, 2};
sort(p, 9);
for (i = 0; i < 9; i++)
{
printf("%d\t", p[i]);
}
printf("\n");
}
/*
*实现两个有序数组的归并
*
*/
int *merger(int *arr1, int length1, int *arr2, int length2)
{
int i = 0;
int j = 0;
int k = 0;
int *arr = NULL;
arr = (int *)malloc(sizeof(int)*(length1+length2));
if (NULL == arr)
{
arr = NULL;
goto exit;
}
while (i < length1 && j < length2)
{
if (arr1[i] < arr2[j])
{
arr[k++] = arr1[i++];
}
else
{
arr[k++] = arr2[j++];
}
}
while (i < length1)
{
arr[k++] = arr1[i++];
}
while (j < length2)
{
arr[k++] = arr2[j++];
}
exit:
return arr;
}
void sort(int *arr, int length)
{
int length1, length2;
int *arr1, *arr2;
int *p;
if (length > 1)
{
length1 = length/2;
length2 = length - length1;
arr1 = arr;
arr2 = arr+length1;
sort(arr1, length1);
sort(arr2, length2);
p = merger(arr1, length1, arr2, length2);
}
arr = p;
}
能写下归并排序么？

Answer 1

题目是有序数组，所以a,b两数组是已排序好的，否则，sort函数应为以a，b进行排序，再归并，
以下代码去掉了sort的函数
#include <stdio.h>
#include <malloc.h>
int *merger(int *arr1, int length1, int *arr2, int length2);
//void sort(int *arr, int length);
int main(void)
{
int i;
/* 测试merger的归并效果 */
int a[5] = { 1,3, 5, 7, 9};
int b[4] = {2, 4,6, 8};
for (i = 0; i < 5; i++)
printf("%d\t", a[i]);
printf("\n");
for (i = 0; i < 4; i++)
printf("%d\t", b[i]);
printf("\n");
int *p= NULL;
p = merger(a, 5, b, 4); /* *实现两个有序数组的归并 */
for (i = 0; i <9; i++)
printf("%d\t", p[i]);
printf("\n");
//sort(p, 9);
return 0;
}

int *merger(int *arr1, int length1, int *arr2, int length2)
{
int i = 0;
int j = 0;
int k = 0;
int *arr = NULL;
arr = (int *)malloc(sizeof(int)*(length1+length2));
if (NULL == arr)
return 0; //一般不用goto
while (i < length1 && j < length2)
{
if (arr1[i] < arr2[j])
arr[k++] = arr1[i++];
else
arr[k++] = arr2[j++];
}
while (i < length1)
arr[k++] = arr1[i++];
while (j < length2)
arr[k++] = arr2[j++];
return arr;
}追问

非常感谢你的回答。
1、题目不是归并，而是归并排序，所以sort是非常有必要的
2、goto一般是为了保证程序的单出口，所以还是很常用到的

Answer 2

写个排序的算法吧
void sort(int *arr, int length)
{ int i=0；
int maxPosition=0;
int tempValue,maxValue;
if(length==1）
{
// 已经是排序好的啦
}
if(length>1)
{
maxPosition=0;
maxValue=*arr;
for(i=0;i<length;i++)
{
if(maxValue<*(arr+i)
{
maxValue=*(arr+i);
maxPosition=i;
}
}
tempValue=*(arr+length-1);
*(arr+leng-1)=maxValue;
*(arr+maxPosition-1)=tempValue;
sort(*arr, length-1)

}

}追问

不好意思没看懂你的程序用的是什么算法，你的程序应该是没经过测试的，程序中出现中文的符号，首先编译就不能通过了。最后一行的sort中sort的第一个参数传的应该是地址吧，不明白你为什么要取内容？

追答

我只是写了程序流程，来表示怎么用递归来排序，主要的算法就是每次找到一组数中的最大数，然后放到数的最后。

追问

那这个是冒泡排序了，能否写下归并排序，行的话分就给你了

Answer 3

最后的arr = p;只把sort函数中的arr指针指向了p,不会改变调用它的地方（main中的p）的指针，mian 中的p还指向原来的地址，内容不会修改本回答被提问者采纳

Answer 4

你的归并函数不是要归并两个有序的数组吗？为什么你传进来的两个数据都是无序的？

Answer 5

并归算法是什么？