以下代碼經測試,排序5000000(五千萬)int型數據沒有問題!
第一個參數是數組首地址
第二個參數是數組元素個數
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<number; step*=2)
{
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<step)
{
tmpArr[i++] = arr[index1+tmpIndex1];
tmpIndex1++;
}
while ((tmpIndex2<step) && ((index2+tmpIndex2) < number))
{
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 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<number; step*=2)
{
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<step)
{
tmpArr[i++] = arr[index1+tmpIndex1];
tmpIndex1++;
}
while ((tmpIndex2<step) && ((index2+tmpIndex2) < number))
{
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);
}
測試代碼:
#include <stdio.h>
#include <conio.h>
#include <windows.h>
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<num; 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<number; step*=2)
{
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<step)
{
tmpArr[i++] = arr[index1+tmpIndex1];
tmpIndex1++;
}
while ((tmpIndex2<step) && ((index2+tmpIndex2) < number))
{
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<number; i++,j++)
{
if (arr[i] > arr[j])
{
printf("第%u個數大於第%u個數!\n", i, j);
return;
}
}
}
#include <stdio.h>
#include <conio.h>
#include <windows.h>
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<num; 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<number; step*=2)
{
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<step)
{
tmpArr[i++] = arr[index1+tmpIndex1];
tmpIndex1++;
}
while ((tmpIndex2<step) && ((index2+tmpIndex2) < number))
{
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<number; i++,j++)
{
if (arr[i] > arr[j])
{
printf("第%u個數大於第%u個數!\n", i, j);
return;
}
}
}
摘自 kevinshq的專欄