您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

非遞歸堆排序算法：C 語言高性能實現與百萬級測試

編輯：關於C

算法原理

堆排序利用**完全二叉樹**性質，將陣列視為堆結構。分兩階段：

建堆：自底向上調整，構建大根堆 (父節點 ≥ 子節點)。
排序：反覆交換堆頂 (最大值) 與堆尾元素，縮小堆範圍，向下調整新堆頂。

非遞歸實現避免函數調用開銷，適合嵌入式、高性能場景。

核心代碼實現


#include <windows.h> // DWORD 類型

// 參數: arr 陣列首址, number 元素個數
void HeapSort(int * const arr, const DWORD number)
{
    if (number < 2) return;

    int tmp;
    DWORD tmpIndex, indexUp, indexDown, num;

    // === 階段 1: 建堆 (自底向上) ===
    indexUp = number - 1; // 最後一個葉子節點索引

    // 處理最後一個非滿雙子節點的父節點 (若總數為偶數)
    if (indexUp % 2 != 0)
    {
        tmpIndex = (indexUp - 1) / 2; // 父節點
        if (arr[indexUp] > arr[tmpIndex]) { /* 交換 */ }
        indexUp--;
    }

    // 成對處理剩餘父節點 (每次處理一對兄弟節點)
    for (; indexUp > 0; indexUp -= 2)
    {
        tmpIndex = (indexUp / 2) - 1; // 父節點
        // 找較大的子節點
        if (arr[indexUp - 1] >= arr[indexUp])
        {
            if (arr[indexUp - 1] > arr[tmpIndex]) { indexDown = indexUp - 1; /* 交換父子 */ }
            else continue;
        }
        else
        {
            if (arr[indexUp] > arr[tmpIndex]) { indexDown = indexUp; /* 交換父子 */ }
            else continue;
        }

        // 向下篩選 (Sift Down)
        while ((2 * indexDown) < number)
        {
            tmpIndex = 2 * indexDown + 1; // 左子節點
            // 選較大的子節點 (注意右子節點邊界)
            if (arr[tmpIndex] >= arr[tmpIndex + 1] || (tmpIndex + 1 == number))
            {
                if (arr[tmpIndex] > arr[indexDown]) { /* 交換並下沉 */ indexDown = tmpIndex; }
                else break;
            }
            else
            {
                if (arr[tmpIndex + 1] > arr[indexDown]) { /* 交換並下沉 */ indexDown = tmpIndex + 1; }
                else break;
            }
        }
    }

    // === 階段 2: 排序 (反覆取最大) ===
    // 將堆頂 (最大) 與當前堆尾交換
    tmp = arr[0]; arr[0] = arr[number - 1]; arr[number - 1] = tmp;

    for (num = number - 1; num > 1; num--)
    {
        indexDown = 0;
        // 向下調整新堆頂
        while ((2 * indexDown + 1) < num)
        {
            tmpIndex = 2 * indexDown + 1;
            if (arr[tmpIndex] >= arr[tmpIndex + 1])
            {
                if (arr[tmpIndex] > arr[indexDown]) { /* 交換並下沉 */ indexDown = tmpIndex; }
                else break;
            }
            else
            {
                if ((arr[tmpIndex + 1] > arr[indexDown]) && (tmpIndex + 1 < num)) { /* 交換並下沉 */ 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 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");
}

int main()
{
    DWORD StartTime, EndTime, i;
    DWORD num = 50000000; // 5000 萬
    int *arr = (int *)malloc(num * sizeof(int));
    if (!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;
}