非遞歸堆排序演算法實現與效能測試

編輯：關於C語言

非遞歸堆排序演算法深度解析

堆排序是一種基於二叉堆資料結構的選擇排序演算法，具有 O(n log n) 的時間複雜度且空間複雜度為 O(1)。本文介紹一個經過大規模測試的非遞歸堆排序 C 語言實現，可穩定處理 5,000 萬筆整數資料。

核心程式碼實現

void HeapSort(int * const arr, const DWORD number) {
    int tmp;
    DWORD tmpIndex, i = 1, num, indexUp, 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 <stdlib.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, i;
    DWORD num = 50000000;
    int *arr = (int *)malloc(num * sizeof(int));
    
    if (NULL == arr) {
        printf("記憶體配置失敗，程式結束！\n");
        return -1;
    }
    
    // 產生隨機資料
    StartTime = GetTickCount();
    for (i = 0; i < num; i++) arr[i] = rand();
    EndTime = GetTickCount();
    printf("產生 %u 個隨機數耗時：%u ms\n", num, EndTime - StartTime);
    
    // 執行堆排序
    StartTime = GetTickCount();
    HeapSort(arr, num);
    EndTime = GetTickCount();
    printf("堆排序耗時：%u ms\n", EndTime - StartTime);
    
    // 驗證排序結果
    ExamineArr(arr, num);
    free(arr);
    return 0;
}

void ExamineArr(const int * const arr, DWORD number) {
    for (DWORD i = 0, j = 1; j < number; i++, j++) {
        if (arr[i] > arr[j]) {
            printf("第 %u 個數大於第 %u 個數！\n", i, j);
            return;
        }
    }
    printf("排序驗證通過！\n");
}