|
#include<stdio.h>
#include<stdlib.h>//分配内存
#include<time.h>
typedef?int?ElemType;
const?int?N?=?10000;
ElemType?arr[N];
ElemType?n;
void?Merge(ElemType?arr[],?ElemType?tempArr[],?int?left,?int?mid,?int?right)//合并
{
????//标记左半区第一个未排序元素
????int?l_pos?=?left;
????//标记右半区第一个未排序的元素
????int?r_pos?=?mid?+?1;
????//临时数组元素下标
????int?pos?=?left;
????//合并
????while?(l_pos?<=?mid?&&?r_pos?<=?right)
????{
????????if?(arr[l_pos]?<?arr[r_pos])
????????????tempArr[pos++]?=?arr[l_pos++];
????????else
????????????tempArr[pos++]?=?arr[r_pos++];
????}
????//合并左半区剩余元素
????while?(l_pos?<=?mid)
????????tempArr[pos++]?=?arr[l_pos++];
????//合并右半区剩余元素
????while?(r_pos?<=?right)
????????tempArr[pos++]?=?arr[r_pos++];
????//把临时数组中合并后的元素复制回原来的数组
????while?(left?<=right)
????{
????????arr[left]?=?tempArr[left];
????????left++;
????}
}
void?Msort(ElemType?arr[],?ElemType?tempArr[],?int?left,?int?right)
{
????if?(left?<?right)
????{
????????//找中间点
????????int?mid?=?(left?+?right)?/?2;
????????//递归划分左半区
????????Msort(arr,?tempArr,?left,?mid);
????????//递归划分右半区
????????Msort(arr,?tempArr,?mid?+?1,?right);
????????//合并已经排序的部分
????????Merge(arr,?tempArr,?left,?mid,?right);
????}
}
void?MergeSort(ElemType?arr[],?ElemType?n)
{
????int*?tempArr?=?(ElemType*)malloc(n?*?sizeof(ElemType));
????if?(tempArr)//分配成功
????{
????????Msort(arr,?tempArr,?0,?n?-?1);
????????free(tempArr);
????}
????else
????{
????????printf("分配内存失败");
????}
}
//随机输入
void?Randinit()
{
????scanf("%d",&n);//输入个数
????srand((int)time(NULL));
????for?(int?i?=?0;?i?<?n;?++i)
????{
????????arr[i]?=?rand();//随机输入
????????printf("%d?",arr[i]);
????}
????printf("\n");
}
//输出
void?print()
?
{
????printf("\n");//换行
????for?(int?i?=?0;?i?<?n;?++i)//遍历输出
????????printf("%d?",arr[i]);
?????printf("\n");
}
int?main()
{
????Randinit();//随机输入
????MergeSort(arr,?n);
????print();
????return?0;
}
|