面试题：请介绍下std::sort的原理？底层是快速排序吗？

std::sort 是 C++ 标准库中用于对容器（如 std::vector、std::array 等）或范围进行排序的算法。它的实现原理和底层排序算法并不是固定的快速排序，而是一种混合排序算法，结合了多种排序算法的优点，以达到较高的性能和稳定性。

`std::sort` 的原理

算法选择：
- std::sort 并不是单一算法的实现，而是一种混合排序算法（Hybrid Sorting Algorithm）。
- 它通常结合了快速排序（QuickSort）、**堆排序（HeapSort）和插入排序（Insertion Sort）**的优点。
具体实现：
- 快速排序：作为主要排序算法，快速排序的平均时间复杂度为 O(nlog⁡n)O(nlogn)，但在最坏情况下（如已经有序的数组）会退化为 O(n2)O(n2)。
- 堆排序：为了避免快速排序的最坏情况，std::sort 在递归深度超过一定阈值时，会切换到堆排序。堆排序的时间复杂度始终为 O(nlog⁡n)O(nlogn)，适合处理大规模数据。
- 插入排序：对于小规模数据（如元素数量少于某个阈值，通常是 16 或 32），std::sort 会切换到插入排序。插入排序在小数据量上表现优异，且是稳定的排序算法。
递归深度控制：
- std::sort 会监控递归深度，如果递归过深（接近最坏情况），则切换到堆排序，避免快速排序的性能退化。
分区优化：
- 在快速排序的分区过程中，std::sort 通常使用三数取中法（Median-of-Three）或随机化分区来选择基准值（pivot），以减少最坏情况发生的概率。

时间复杂度

平均情况：O(nlog⁡n)O(nlogn)
最坏情况：O(nlog⁡n)O(nlogn)（由于堆排序的介入，避免了快速排序的最坏情况）

空间复杂度

快速排序：通常是原地排序，空间复杂度为 O(log⁡n)O(logn)（递归栈空间）。
堆排序：空间复杂度为 O(1)O(1)。
插入排序：空间复杂度为 O(1)O(1)。

因此，std::sort 的整体空间复杂度为 O(log⁡n)O(logn)。

稳定性

std::sort 不是稳定的排序算法。如果需要稳定排序，可以使用 std::stable_sort。

示例代码

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    std::sort(vec.begin(), vec.end());

    for (int num : vec) {
        std::cout << num << " ";
    }
    return 0;
}

输出：