您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計疑難解答

C++ 快速排序記憶體錯誤：常見陷阱與標準實作參考

編輯：程式設計疑難解答

C++ 手寫 QuickSort 常因分區邏輯錯誤、索引越界、遞迴終止條件缺失導致記憶體錯誤（Access Violation / Segmentation Fault / Heap Corruption）。本文列舉典型錯誤並提供經過測試的標準實作。

典型錯誤模式

錯誤代碼片段	後果
`pivot = arr[high];` 但 `high` 可能超出陣列	讀取越界 → Access Violation
`while (i < j) { while (arr[i] < pivot) i++; ... }` 缺少 `i < high` 保護	指標跑飛 → Heap Corruption
遞迴呼叫 `quickSort(arr, low, pi)` 未排除 `pi` 自身	無限遞迴 → Stack Overflow
分區函式回傳 `int` 但用 `size_t` 索引，負數轉大數	索引環繞 → 越界
原始陣列傳 `int*` 但函式簽名用 `vector&` 不匹配	編譯錯誤/未定義行為

標準 QuickSort 實作（含隨機化 pivot、尾部遞迴優化）

#include 
#include 
#include 

template 
void quickSort(RandomIt first, RandomIt last) {
    if (std::distance(first, last) < 2) return;  // 0 或 1 元素直接返回

    // 隨機選 pivot 避免最壞 O(n²)
    std::uniform_int_distribution<> dist(0, std::distance(first, last) - 1);
    std::advance(first, dist(std::mt19937{std::random_device{}()}));
    auto pivot = *first;
    std::iter_swap(first, last - 1);  // pivot 移到末尾

    // 三向切分：< pivot | == pivot | > pivot
    RandomIt lt = first, gt = last - 1, i = first;
    while (i != gt) {
        if (*i < pivot) { std::iter_swap(lt++, i++); }
        else if (*i > pivot) { std::iter_swap(i, --gt); }
        else { ++i; }
    }
    std::iter_swap(gt, last - 1);  // pivot 歸位

    // 尾部遞迴優化：先排較小分區
    auto leftSize  = std::distance(first, lt);
    auto rightSize = std::distance(gt + 1, last);
    if (leftSize < rightSize) {
        quickSort(first, lt);
        quickSort(gt + 1, last);
    } else {
        quickSort(gt + 1, last);
        quickSort(first, lt);
    }
}

// 使用範例
int main() {
    std::vector v = {9, 3, 5, 1, 7, 2, 8, 4, 6, 0};
    quickSort(v.begin(), v.end());
    for (int x : v) std::cout << x << ' ';  // 0 1 2 3 4 5 6 7 8 9
}

教學用簡化版（陣列指標、單向切分、易理解）

void quickSort(int *arr, int low, int high) {
    if (low >= high) return;                 // 終止條件

    int pivot = arr[low + (high - low) / 2]; // 中間元素做 pivot
    int i = low, j = high;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            std::swap(arr[i++], arr[j--]);
        }
    }
    if (low < j)  quickSort(arr, low, j);    // 左半
    if (i < high) quickSort(arr, i, high);   // 右半
}

// 呼叫
int a[] = {9,3,5,1,7,2,8,4,6,0};
quickSort(a, 0, 9);

除錯技巧

**加入斷言**：`assert(low >= 0 && high < size);`
**列印分區過程**：`std::cerr << "partition: low=" << low << " high=" << high << " pivot=" << pivot << '\n';`
**使用 AddressSanitizer**：`g++ -fsanitize=address -g quicksort.cpp`，執行時自動偵測越界/使用後釋放
**單元測試**：空陣列、單元素、已排序、逆序、重複元素、大陣列（10⁶）

生產環境建議

**不要手寫排序**。直接用標準庫：

#include 
std::sort(v.begin(), v.end());           // Introsort (QuickSort+HeapSort+InsertionSort)
std::stable_sort(v.begin(), v.end());    // 穩定排序 (MergeSort)

掌握分區邏輯邊界條件、終止條件、隨機化 pivot、尾部遞迴優化，即可寫出無記憶體錯誤的 QuickSort；實務上請直接用 `std::sort`。