爱华网//划分待排序数据为左右两部分，比较左右两部分。存入临时数组
//将排序好的数据在临时数组中copy到原数组中
//
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
void
print_array(int *array_test,unsigned int x)
{
unsigned int i;
for(i=0;i<x;i++)
{
printf(" %d ",array_test[i]);
}
printf("n");
}
static void
merge(int array[], int low, int mid, int high)
{
int i, k;
int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
int begin1 = low; //左半边开始下标
int end1 = mid; //左半边结束下标
int begin2 = mid + 1; //右半边开始下标
int end2 = high; //右半边开始下标
printf("mid = %d",mid);
//由于begin1 end1 begin2 end2 中都有需要比较的元素，故需要 <=
for (k = 0; begin1 <= end1 && begin2 <= end2; k++) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
{
if(array[begin1]<array[begin2]) //左右两边分别比较，并且一次存入零时数组中
{
temp[k] = array[begin1++];
}
else
{
temp[k] = array[begin2++];
}
}
//由于begin1 end1 begin2 end2 中都有需要比较的元素，故需要 <=
while(begin1<=end1)//若第一个序列有剩余，直接拷贝出来粘到合并序列尾
{
temp[k++] = array[begin1++];
}
while(begin2<=end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
{
temp[k++] = array[begin2++];
}
for (i = 0; i < (high-low+1); i++)//将排序好的序列拷贝回数组中
{
array[low+i] = temp[i];
}
printf("合并： ");
print_array(array,MAX);
free(temp);
}
void
merge_sort(int array[], unsigned int first, unsigned int last)
{
int mid = 0;
if(first<last)
{
mid = (first+last)/2;
merge_sort(array, first, mid);//划分左半部分
merge_sort(array, mid+1,last);//划分右半部分
merge(array,first,mid,last);//合并
}
}
int main(void)
{
int array_test[MAX] = {0,9,8,7,6,5,4,3,2,1};
printf("start: ");
print_array(array_test,MAX);
merge_sort(array_test,0,MAX-1);
printf("end: ");
print_array(array_test,MAX);
return 0;
}
