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

插入排序算法原理與 C++ 高精度計時實現詳解

編輯：關於C

前言

插入排序是一種直觀、穩定的基礎排序算法，適合小規模或近乎有序數據。本文結合《算法導論》偽代碼，詳細解析其邏輯，並提供一個基於 Windows API 的高精度計時 C++ 實現，幫助理解算法性能特徵。

一、算法核心思想

插入排序模擬「整理撲克牌」過程：將數組分為已排序區與未排序區，每次從未排序區取出首元素，在已排序區中從右向左比較、位移，找到合適位置插入。

二、關鍵步驟圖解

以數組 {4, 2, 7, 1, 8, 9, 6} 為例：

初始: [4] | 2 7 1 8 9 6
i=1:  [2 4] | 7 1 8 9 6  (2 插入 4 前)
i=2:  [2 4 7] | 1 8 9 6  (7 保持)
i=3:  [1 2 4 7] | 8 9 6  (1 移至首位)
i=4:  [1 2 4 7 8] | 9 6  (8 保持)
i=5:  [1 2 4 7 8 9] | 6  (9 保持)
i=6:  [1 2 4 6 7 8 9] |   (6 插入 7 前)
最終: 1 2 4 6 7 8 9

三、《算法導論》偽代碼對照

INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

對應 C++ 實現：

for (int j = 1; j < n; j++) {  // C++ 0-based 索引
    int key = arr[j];
    int i = j - 1;
    while (i >= 0 && arr[i] > key) {
        arr[i+1] = arr[i];  // 右移
        i--;
    }
    arr[i+1] = key;  // 插入
}

四、高精度計時實現（Windows 平台）

使用 QueryPerformanceCounter 獲取 CPU 週期級計時：

#include 
#include 
#include 

int main() {
    int arr[] = {4,2,7,1,8,9,6};
    const int n = sizeof(arr)/sizeof(arr[0]);

    LARGE_INTEGER freq, start, end;
    QueryPerformanceFrequency(&freq);  // 獲取頻率
    QueryPerformanceCounter(&start);   // 開始計時

    // 插入排序核心代碼
    for (int j = 1; j < n; j++) {
        int key = arr[j];
        int i = j - 1;
        while (i >= 0 && arr[i] > key) {
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = key;
    }

    QueryPerformanceCounter(&end);     // 結束計時
    double elapsed_ms = (double)(end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;

    std::cout << "排序結果: ";
    for (int i = 0; i < n; i++) std::cout << arr[i] << ' ';
    std::cout << "\n耗時: " << std::fixed << std::setprecision(3) << elapsed_ms << " ms\n";
    return 0;
}

關鍵點：

QuadPart 為 64 位整數，避免溢出。
頻率 freq 通常為 CPU 主頻（如 3.0 GHz ≈ 3×10⁹ Hz）。
微秒級精度滿足算法分析需求。

五、複雜度與特性分析

指標	數值	說明
最好時間	O(n)	已有序，僅比較不移動
最壞時間	O(n²)	逆序，每輪需移動所有已排序元素
平均時間	O(n²)
空間複雜度	O(1)	原地排序
穩定性	穩定	相等元素相對順序不變
適應性	強	近乎有序時極快