归并排序出现问题,请教高手,谢谢
#include<stdio.h>#include<time.h>
#include<stdlib.h>
#define M (30)
int array[M] = {0};
int* Malloc(int beg,int end)
{
int* p = NULL;
p = (int*)malloc(end-beg+1);
if(NULL == p)
{
perror("malloc");
exit (-1);
}
return p;
}
//升序函数
/**************************************************
归并操作的工作原理如下:
1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
******************************************/
void merge(int beg,int mid,int end)
{
int k = 0;
int *temp = Malloc(beg,end);
printf("malloc size =%d\n",end-beg+1);
int first1 = beg;
int first2 = mid+1;
while(first1 <= mid && first2 <= end)
{
if(array[first1] < array[first2])
temp[k++] = array[first1++];
else
temp[k++] = array[first2++];
}
while(first1 <= mid)
temp[k++] = array[first1++];
while(first2 <= end)
temp[k++] = array[first2++];
for(k=0;k<(end-beg+1);++k)
array[beg+k] = temp[k];
free(temp);
}
/*********************************************
* 函数名称:void merge_sort(int *array,int beg,int end)
* 函数作用:使数组array从beg开始到end使升序的
* 函数作者:
* 完成日期:2010.11.2
* ************************************************/
void merge_sort(int beg,int end)
{
int mid = 0;
if(beg == end)
return;
else
{
mid = (beg + end)/2;
merge_sort(beg,mid);
merge_sort(mid+1,end);
merge(beg,mid,end); //升序函数
}
}
void print(int *array)
{
int i=0;
for(i=0;i<M;++i)
{
printf("%d\n",array[i]);
}
}
int main()
{
srand((int)time(0));
int i = 0 ;
for(i=0;i<M;++i)
{
array[i] = rand()%1000;
}
merge_sort(0,M-1);
print(array);
}
如果M值小一点,输出是正确的,但是一旦M值较大,则输出出错,望懂得人能告诉小弟,不胜感激