内省排序
入门工程实践中最常用的排序算法，理解"混合策略"的价值。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void introSort(int arr[], int n) {
2 int depthLimit = 2 * log2(n);
3 function<void(int, int, int)> sort = [&](int lo, int hi, int depth) {
4 if (hi - lo < 16) {
5 insertionSort(arr + lo, hi - lo + 1);
6 return;
7 }
8 if (depth == 0) {
9 make_heap(arr + lo, arr + hi + 1);
10 sort_heap(arr + lo, arr + hi + 1);
11 return;
12 }
13 int pivot = partition(arr, lo, hi);
14 sort(lo, pivot - 1, depth - 1);
15 sort(pivot + 1, hi, depth - 1);
16 };
17 sort(0, n - 1, depthLimit);
18}
复杂度分析
时间 O(n log n)
空间 O(log n)
最优 O(n log n)
最坏 O(n log n)
算法讲解
内省排序以快排为主，当递归深度超过阈值时切换为堆排序。
当分区大小小于阈值时，使用插入排序（对小数组更高效）。
这种混合策略避免了快排的最坏情况，同时保持了平均性能。
C++ STL 的 std::sort 和 Java 的 Arrays.sort 都使用类似策略。