ULL;
arr = (int *)malloc(num * sizeof (int));
if (NULL == arr)
{
free(arr);
printf("内存分配失败，程序退出！\n");
getch();
return -1;
}
StartTime = GetTickCount();
for (i=0; i {
*(arr+i) = rand();
}
EndTime = GetTickCount();
printf("生成%u个随机数耗时：%ums\n", num, EndTime - StartTime);
StartTime = GetTickCount();
MergeSort(arr, num);
EndTime = GetTickCount();
printf("归并排序耗时：%ums\n", EndTime - StartTime);
ExamineArr(arr, num);//检查排序结果
free(arr);
getch();
return 0;
}
void MergeSort(int * const arr, const DWORD number)//归并排序
{
DWORD i;
DWORD index1, index2;//将数组分为两个，分别作为两个数组第一个元素的下标
DWORD tmpIndex1, tmpIndex2;//分别指向两个数组中的元素相对于index1、index2的步进
DWORD step;//步进
int *tmpArr = NULL;
if (number < 2)
{
return;
}
tmpArr = (int *)malloc(number*sizeof (int));
if (NULL == tmpArr)
{
printf("分配缓存出错！\n");
getch();
return;
}
for (step=1; step {
index1 = 0;
index2 = index1 + step;
tmpIndex1 = 0;
tmpIndex2 = 0;
i = 0;
while ((index2+tmpIndex2) < number)
{
while ((tmpIndex1 < step) && (tmpIndex2 < step) && ((index2+tmpIndex2) < number))
{
if (arr[index1+tmpIndex1] <= arr[index2+tmpIndex2])
{
tmpArr[i] = arr[index1+tmpIndex1];
tmpIndex1++;
}
else
{
tmpArr[i] = arr[index2+tmpIndex2];
tmpIndex2++;
}
i++;
}
while (tmpIndex1 {
tmpArr[i++] = arr[index1+tmpIndex1];
tmpIndex1++;
}
while ((tmpIndex2 {
tmpArr[i++] = arr[index2+tmpIndex2];
tmpIndex2++;
}
index1 = index1 + 2*step;
index2 = index2 + 2*step;
tmpIndex1 = 0;
tmpIndex2 = 0;
}
memcpy(arr, tmpArr, number*sizeof (int));
}
free(tmpArr);
}
void ExamineArr(const int * const arr, DWORD number)
{
DWORD i=0, j=1;
if (number <2)
{
return;
}
for (; j {
if (arr[i] > arr[j])
{
printf("第%u个数大于第%u个数！\n", i, j);
return;
}
}
}
#include
#include
#include
void MergeSort(int * const arr, const DWORD number);//归并排序
void ExamineArr(const int * const arr, DWORD number);//检查排序结果
int main(int argc, char *argv[])
{
DWORD StartTime, EndTime;
DWORD i;
DWORD num = 50000000;
int *arr = NULL;
arr = (int *)malloc(num * sizeof (int));
if (NULL == arr)
{
free(arr);
printf("内存分配失败，程序退出！\n");
getch();
return -1;
}
StartTime = GetTickCount();
for (i=0; i {
*(arr+i) = rand();
}
EndTime = GetTickCount();
printf("生成%u个随机数耗时：%ums\n", num, EndTime - StartTime);
StartTime = GetTickCount();
MergeSort(arr, num);
EndTime = GetTickCount();
printf("归并排序耗时：%ums\n", EndTime - StartTime);
ExamineArr(arr, num);//检查排序结果
free(arr);
getch();
return 0;
}
void MergeSort(int * const arr, const DWORD number)//归并排序
{
DWORD i;
DWORD index1, index2;//将数组分为两个，分别作为两个数组第一个元素的下标
DWORD tmpIndex1, tmpIndex2;//分别指向两个数组中的元素相对于index1、index2的步进 |