堆排序（非遞歸）

以下代碼經測試，排序5000000（五千萬）int型數據沒有問題！

第一個參數是數組首地址
第二個參數是數組元素個數
void HeapSort(int * const arr, const DWORD number)//堆排序  
{ 
    int tmp; 
    DWORD tmpIndex; 
    DWORD i=1; 
    DWORD num; 
    DWORD indexUp; 
    DWORD indexDown; 
    if (number < 2) 
    { 
        return; 
    } 
    indexUp = number-1; 
    if (0 != (indexUp%2)) 
    { 
        tmpIndex = (indexUp - 1) / 2; 
        if (arr[indexUp] > arr[tmpIndex]) 
        { 
            tmp = arr[indexUp]; 
            arr[indexUp] = arr[tmpIndex]; 
            arr[tmpIndex] = tmp; 
        } 
        indexUp--; 
    } 
    for (; indexUp>0; indexUp-=2) 
    { 
        tmpIndex = (indexUp / 2) - 1; 
        if (arr[indexUp-1] >= arr[indexUp]) 
        { 
            if (arr[indexUp-1] > arr[tmpIndex]) 
            { 
                tmp = arr[indexUp-1]; 
                arr[indexUp-1] = arr[tmpIndex]; 
                arr[tmpIndex] = tmp; 
                indexDown = indexUp-1; 
            } 
            else 
            { 
                continue; 
            } 
        } 
        else 
        { 
            if (arr[indexUp] > arr[tmpIndex]) 
            { 
                tmp = arr[indexUp]; 
                arr[indexUp] = arr[tmpIndex]; 
                arr[tmpIndex] = tmp; 
                indexDown = indexUp; 
            } 
            else 
            { 
                continue; 
            } 
        } 
        while ((2*indexDown) < number) 
        { 
            tmpIndex = 2*indexDown +1; 
            if (arr[tmpIndex] >= arr[tmpIndex+1] || (tmpIndex+1 == number)) 
            { 
                if (arr[tmpIndex] > arr[indexDown]) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex]; 
                    arr[tmpIndex] = tmp; 
                    indexDown = tmpIndex; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            else 
            { 
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex < number)) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex+1]; 
                    arr[tmpIndex+1] = tmp; 
                    indexDown = tmpIndex+1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
        } 
    } 
    tmp = arr[0]; 
    arr[0] = arr[number-1]; 
    arr[number-1] = tmp; 
 
    for (num=number-1; num>1; num--) 
    { 
        for (indexDown=0; (2*indexDown +1) < num; ) 
        { 
            tmpIndex = 2*indexDown +1; 
            if (arr[tmpIndex] >= arr[tmpIndex+1]) 
            { 
                if (arr[tmpIndex] > arr[indexDown]) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex]; 
                    arr[tmpIndex] = tmp; 
                    indexDown = tmpIndex; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            else 
            { 
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex+1 < num)) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex+1]; 
                    arr[tmpIndex+1] = tmp; 
                    indexDown = tmpIndex+1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
        } 
        tmp = arr[0]; 
        arr[0] = arr[num-1]; 
        arr[num-1] = tmp; 
    } 
} 
void HeapSort(int * const arr, const DWORD number)//堆排序
{
    int tmp;
    DWORD tmpIndex;
    DWORD i=1;
    DWORD num;
    DWORD indexUp;
    DWORD indexDown;
    if (number < 2)
    {
        return;
    }
    indexUp = number-1;
    if (0 != (indexUp%2))
    {
        tmpIndex = (indexUp - 1) / 2;
        if (arr[indexUp] > arr[tmpIndex])
        {
            tmp = arr[indexUp];
            arr[indexUp] = arr[tmpIndex];
            arr[tmpIndex] = tmp;
        }
        indexUp--;
    }
    for (; indexUp>0; indexUp-=2)
    {
        tmpIndex = (indexUp / 2) - 1;
        if (arr[indexUp-1] >= arr[indexUp])
        {
            if (arr[indexUp-1] > arr[tmpIndex])
            {
                tmp = arr[indexUp-1];
                arr[indexUp-1] = arr[tmpIndex];
                arr[tmpIndex] = tmp;
                indexDown = indexUp-1;
            }
            else
            {
                continue;
            }
        }
        else
        {
            if (arr[indexUp] > arr[tmpIndex])
            {
                tmp = arr[indexUp];
                arr[indexUp] = arr[tmpIndex];
                arr[tmpIndex] = tmp;
                indexDown = indexUp;
            }
            else
            {
                continue;
            }
        }
        while ((2*indexDown) < number)
        {
            tmpIndex = 2*indexDown +1;
            if (arr[tmpIndex] >= arr[tmpIndex+1] || (tmpIndex+1 == number))
            {
                if (arr[tmpIndex] > arr[indexDown])
                {
                    tmp = arr[indexDown];
                    arr[indexDown] = arr[tmpIndex];
                    arr[tmpIndex] = tmp;
                    indexDown = tmpIndex;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex < number))
                {
                    tmp = arr[indexDown];
                    arr[indexDown] = arr[tmpIndex+1];
                    arr[tmpIndex+1] = tmp;
                    indexDown = tmpIndex+1;
                }
                else
                {
                    break;
                }
            }
        }
    }
    tmp = arr[0];
    arr[0] = arr[number-1];
    arr[number-1] = tmp;

    for (num=number-1; num>1; num--)
    {
        for (indexDown=0; (2*indexDown +1) < num; )
        {
            tmpIndex = 2*indexDown +1;
            if (arr[tmpIndex] >= arr[tmpIndex+1])
            {
                if (arr[tmpIndex] > arr[indexDown])
                {
                    tmp = arr[indexDown];
                    arr[indexDown] = arr[tmpIndex];
                    arr[tmpIndex] = tmp;
                    indexDown = tmpIndex;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex+1 < num))
                {
                    tmp = arr[indexDown];
                    arr[indexDown] = arr[tmpIndex+1];
                    arr[tmpIndex+1] = tmp;
                    indexDown = tmpIndex+1;
                }
                else
                {
                    break;
                }
            }
        }
        tmp = arr[0];
        arr[0] = arr[num-1];
        arr[num-1] = tmp;
    }
}
測試代碼：

#include <stdio.h>  
#include <conio.h>  
#include <windows.h>  
 
void HeapSort(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(); 
    HeapSort(arr, num); 
    EndTime = GetTickCount(); 
    printf("堆排序耗時：%ums\n", EndTime - StartTime); 
    ExamineArr(arr, num);//檢查排序結果  
 
    free(arr); 
    getch(); 
    return 0; 
} 
 
void HeapSort(int * const arr, const DWORD number)//堆排序  
{ 
    int tmp; 
    DWORD tmpIndex; 
    DWORD i=1; 
    DWORD num; 
    DWORD indexUp; 
    DWORD indexDown; 
    if (number < 2) 
    { 
        return; 
    } 
    indexUp = number-1; 
    if (0 != (indexUp%2)) 
    { 
        tmpIndex = (indexUp - 1) / 2; 
        if (arr[indexUp] > arr[tmpIndex]) 
        { 
            tmp = arr[indexUp]; 
            arr[indexUp] = arr[tmpIndex]; 
            arr[tmpIndex] = tmp; 
        } 
        indexUp--; 
    } 
    for (; indexUp>0; indexUp-=2) 
    { 
        tmpIndex = (indexUp / 2) - 1; 
        if (arr[indexUp-1] >= arr[indexUp]) 
        { 
            if (arr[indexUp-1] > arr[tmpIndex]) 
            { 
                tmp = arr[indexUp-1]; 
                arr[indexUp-1] = arr[tmpIndex]; 
                arr[tmpIndex] = tmp; 
                indexDown = indexUp-1; 
            } 
            else 
            { 
                continue; 
            } 
        } 
        else 
        { 
            if (arr[indexUp] > arr[tmpIndex]) 
            { 
                tmp = arr[indexUp]; 
                arr[indexUp] = arr[tmpIndex]; 
                arr[tmpIndex] = tmp; 
                indexDown = indexUp; 
            } 
            else 
            { 
                continue; 
            } 
        } 
        while ((2*indexDown) < number) 
        { 
            tmpIndex = 2*indexDown +1; 
            if (arr[tmpIndex] >= arr[tmpIndex+1] || (tmpIndex+1 == number)) 
            { 
                if (arr[tmpIndex] > arr[indexDown]) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex]; 
                    arr[tmpIndex] = tmp; 
                    indexDown = tmpIndex; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            else 
            { 
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex < number)) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex+1]; 
                    arr[tmpIndex+1] = tmp; 
                    indexDown = tmpIndex+1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
        } 
    } 
    tmp = arr[0]; 
    arr[0] = arr[number-1]; 
    arr[number-1] = tmp; 
 
    for (num=number-1; num>1; num--) 
    { 
        for (indexDown=0; (2*indexDown +1) < num; ) 
        { 
            tmpIndex = 2*indexDown +1; 
            if (arr[tmpIndex] >= arr[tmpIndex+1]) 
            { 
                if (arr[tmpIndex] > arr[indexDown]) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex]; 
                    arr[tmpIndex] = tmp; 
                    indexDown = tmpIndex; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            else 
            { 
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex+1 < num)) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex+1]; 
                    arr[tmpIndex+1] = tmp; 
                    indexDown = tmpIndex+1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
        } 
        tmp = arr[0]; 
        arr[0] = arr[num-1]; 
        arr[num-1] = tmp; 
    } 
} 
 
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的專欄