排序算法 — 快排、归并、堆排

复杂度总览

算法	最好	平均	最坏	空间	稳定
快速排序	n log n	n log n	n²	log n	❌
归并排序	n log n	n log n	n log n	O(n)	✅
堆排序	n log n	n log n	n log n	O(1)	❌
std::sort	—	n log n	n log n	—	混合(内省)

快速排序

// 分区：选 pivot，小的放左，大的放右
int partition(vector<int> &arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j) {
        if (arr[j] <= pivot) swap(arr[++i], arr[j]);
    }
    swap(arr[i + 1], arr[hi]);
    return i + 1;
}

void quickSort(vector<int> &arr, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
}

退化到 O(n²) 的场景：已排序数组 + 选最后一个元素做 pivot → 每次只减少 1 个元素。

解决：随机选 pivot 或三数取中 → 期望 O(n log n)。

归并排序

void merge(vector<int> &arr, int lo, int mid, int hi) {
    vector<int> left(arr.begin() + lo, arr.begin() + mid + 1);
    vector<int> right(arr.begin() + mid + 1, arr.begin() + hi + 1);
    int i = 0, j = 0, k = lo;
    while (i < left.size() && j < right.size())
        arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
}

void mergeSort(vector<int> &arr, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}

空间 O(n)：需要辅助数组。适合链表排序（不需要额外空间）。

堆排序

void heapify(vector<int> &arr, int n, int i) {
    int largest = i, left = 2 * i + 1, right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int> &arr) {
    int n = arr.size();
    // 建堆 O(n)
    for (int i = n / 2 - 1; i >= 0; --i) heapify(arr, n, i);
    // 排序 O(n log n)
    for (int i = n - 1; i > 0; --i) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

建堆复杂度为什么是 O(n) 而不是 O(n log n)：底层节点多但高度小。数学推导：∑ h/2^h = 2，所以总操作正比于 n。

选择指南

需要稳定？
  ├─ 是 → 归并排序 或 std::stable_sort
  └─ 否 → 内存紧张？
            ├─ 是 → 堆排序
            └─ 否 → 快速排序 / std::sort

std::sort 实际实现：内省排序（IntroSort）
  = 快排 + 递归太深切换堆排 + 小数组切换插入排序