歸並排序（非遞歸）

以下代碼經測試，排序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的專欄