排序算法效能比較程式：Shell、Quick、Heap、Merge 四大排序實作與分析

專案概述

本程式實作四種經典排序算法——Shell Sort、Quick Sort、Heap Sort、Merge Sort，並提供互動式選單系統，支援資料建立、匯入、排序執行、結果顯示與儲存。核心目標是在相同資料集上比較各算法的執行時間、比較次數與移動次數，直觀展示不同算法的效能特徵。

系統架構與資料結構

#define MAXSIZE 2000
typedef struct {
    int key[MAXSIZE];
    int length;
} list;

long int compCount;   // 比較次數計數器
long int shiftCount;  // 移動次數計數器

採用靜態陣列儲存資料，length 記錄實際元素數量。全域計數器用於統計排序過程中的關鍵操作次數。

核心排序算法實作

1. Shell Sort（希爾排序）

list shellsort(list L) {
    compCount = shiftCount = 0;
    int n = L.length, gap = n / 2;
    while (gap > 0) {
        for (int i = gap + 1; i <= n; i++) {
            int j = i - gap;
            while (j > 0) {
                compCount++;
                if (L.key[j] > L.key[j + gap]) {
                    int x = L.key[j]; shiftCount++;
                    L.key[j] = L.key[j + gap]; shiftCount++;
                    L.key[j + gap] = x; shiftCount++;
                    j -= gap;
                } else j = 0;
            }
        }
        gap /= 2;
    }
    return L;
}

採用遞減增量序列，逐步縮小間距進行插入排序，時間複雜度介於 O(n log n) 到 O(n²) 之間。

2. Quick Sort（快速排序）

int Partition(list* pL, int low, int high) {
    pL->key[0] = pL->key[low]; shiftCount++;
    int pivotkey = pL->key[low]; shiftCount++;
    while (low < high) {
        while (low < high && pivotkey <= pL->key[high]) { compCount += 2; --high; }
        pL->key[low] = pL->key[high]; shiftCount++;
        while (low < high && pL->key[low] <= pivotkey) { compCount += 2; ++low; }
        pL->key[high] = pL->key[low]; shiftCount++;
    }
    pL->key[low] = pL->key[0]; shiftCount++;
    return low;
}

void QSort(list* pL, int low, int high) {
    if (low < high) {
        compCount++;
        int pivotloc = Partition(pL, low, high);
        QSort(pL, low, pivotloc - 1);
        QSort(pL, pivotloc + 1, high);
    }
}

list QuickSort(list pL) {
    compCount = shiftCount = 0;
    QSort(&pL, 1, pL.length);
    return pL;
}

採用單軸分區遞迴策略，平均時間複雜度 O(n log n)，最壞情況 O(n²)。以 key[0] 作為暫存哨兵單元。

3. Heap Sort（堆積排序）

void sift(list L, int l, int m) {
    int i = l, j = 2 * i, x = L.key[i];
    while (j <= m) {
        compCount++;
        if (j < m && L.key[j] < L.key[j + 1]) { j++; compCount += 2; }
        if (x < L.key[j]) {
            compCount++;
            L.key[i] = L.key[j]; shiftCount++;
            i = j; shiftCount++;
            j = 2 * i;
        } else j = m + 1;
    }
    L.key[i] = x; shiftCount++;
}

list heapsort(list L) {
    compCount = shiftCount = 0;
    for (int i = L.length / 2; i >= 1; i--) { sift(L, i, L.length); compCount++; }
    for (int i = L.length; i >= 2; i--) {
        compCount++;
        int w = L.key[i]; shiftCount++;
        L.key[i] = L.key[1]; shiftCount++;
        L.key[1] = w; shiftCount++;
        sift(L, i - 1, 1);
    }
    return L;
}

先建立大頂堆，再反覆交換堆頂與末尾元素並調整堆，時間複雜度穩定 O(n log n)，空間複雜度 O(1)。

4. Merge Sort（合併排序）

void Merge(int source[], int result[], int size, int n) {
    int lb1 = 0, p = 0;
    while ((lb1 + size) < n) {
        compCount++;
        int lb2 = lb1 + size, ub1 = lb2 - 1;
        int ub2 = (lb2 + size - 1 > n) ? n - 1 : lb2 + size - 1;
        compCount++; shiftCount++;
        int i = lb1, j = lb2;
        while (i <= ub1 && j <= ub2) {
            compCount += 2;
            if (source[i] <= source[j]) {
                result[p++] = source[i++]; shiftCount++; compCount++;
            } else {
                result[p++] = source[j++]; shiftCount++; compCount++;
            }
        }
        while (i <= ub1) { result[p++] = source[i++]; shiftCount++; compCount++; }
        while (j <= ub2) { result[p++] = source[j++]; shiftCount++; compCount++; }
        lb1 = ub2 + 1;
    }
    while (p < n) { compCount++; result[p++] = source[lb1++]; shiftCount++; }
}

void Mergesort(list* L) {
    int n = L->length, s = 1;
    int* temp = (int*)malloc(n * sizeof(int));
    compCount = shiftCount = 0;
    if (!temp) { printf("out of memory"); return; }
    while (s < n) {
        compCount++;
        Merge(L->key, temp, s, n);
        s *= 2;
        Merge(temp, L->key, s, n);
        s *= 2;
    }
    compCount++;
    free(temp);
}

採用非遞迴自底向上合併策略，需額外 O(n) 暫存空間，時間複雜度穩定 O(n log n)，屬穩定排序。

計時與統計封裝

每種排序皆提供對應的計時包裝函式，如 shell(list L, list* LS, float* timeshell)，使用 clock() 測量 CPU 時間，並輸出耗時、比較次數、移動次數。

互動式選單系統

主程式提供多層選單：

• 主選單：建立資料、匯入檔案、排序、顯示結果、儲存結果、離開
• 排序子選單：單獨執行四種排序或全部執行
• 顯示/儲存子選單：針對各排序結果個別操作

透過 LOCK 旗標控制流程，確保資料就緒後才能排序、排序完成後才能顯示/儲存。

關鍵設計細節與改進建議

• 陣列索引從 1 開始：符合教科書慣例，但需注意 key[0] 作為哨兵用途。
• 全域計數器：簡化統計但非執行緒安全；現代重寫建議封裝於類別內。
• DOS 專用函式：clrscr()、getch()、kbhit() 限制移植性；建議改用跨平台終端機庫。
• 記憶體管理：Merge Sort 動態配置暫存陣列，記得釋放。
• 擴充性：可加入隨機資料產生器、多輪平均計時、圖表化輸出等功能。

總結

本程式完整展示了四大經典排序算法的 C 語言實作與效能比較框架。透過實際執行數據，可觀察到：小資料量時 Shell Sort 表現不錯；大資料量隨機分布下 Quick Sort 平均最快但最壞情況需注意；Heap Sort 保證 O(n log n) 且原地排序；Merge Sort 穩定且適合外部排序擴充。程式結構清晰，適合作為算法教學與效能分析的實驗基礎。