内省排序(Introsort)—— 复刻 C++ 标准库 std::sort 的实现思路

// // 内省排序(Introsort)—— 复刻 C 标准库 std::sort 的实现思路// 单文件完整版,含 main 用例。编译运行:// g -stdc17 -Wall -Wextra main.cpp -o main ./main// 预期输出:all tests passed// // 参考:David Musser 1997 年论文《Introspective Sorting and Selection// Algorithms》 GNU libstdc 头文件 bits/stl_algo.h 的公开实现。//// 为什么叫「内省」?// 普通快速排序平均 O(n log n),但遇到有序/逆序/大量重复这类病态输入// 会退化成 O(n^2)。内省排序给快排装了一面「镜子」,让它边跑边观察// 自己的递归深度:// - 深度正常 - 继续快速排序(主流路径);// - 深度超限 - 判定输入病态,立即改用堆排序(O(n log n) 有保证),// 使整趟排序最坏复杂度锁死在 O(n log n);// - 区间够小 - 改用插入排序(小数组上插入排序常数极小,比快排快)。//// 在「快 堆 插」三件套骨架外,这份实现还叠加了 libstdc 风格的// 6 层优化:// (1) 三点取中选枢轴,并把中位数挪到序列首部,降低退化分区概率;// (2) 未防护(unguarded)双指针相向分区,省掉一半的边界比较;// (3) 递归只处理右边、左边用外层循环迭代,递归深度不翻倍;// (4) 深度上限取 2*lg(n) 而不是 1*lg(n),给快排留两倍余量;// (5) 两阶段插入排序:先带防护排最前 16 个,再对其余元素做「未防护」// 插入排序,利用「快排切完的段与段之间已全局有序」免去边界检查;// (6) 堆排序兜底由「建堆 堆排序」完成(即 partial_sort)。// #includealgorithm#includecassert#includecstdio#includefunctional#includeiterator#includerandom#includeutility#includevectornamespacemy_introsort{// 阈值:区间长度不超过 16 时,插入排序比快排便宜。// (libstdc 的 _S_threshold 正是 16)staticconstexprstd::ptrdiff_t kThreshold16;// ---------------------------------------------------------------// 辅助 1:计算 2*lg(n),即递归深度上限// ---------------------------------------------------------------// lg2(n) 返回「最大的 k,使 2^k n」,等价于 n 的最高二进制位序号。// std::sort 用 __lg(n)*2 做深度上限:// 理想平衡的快排递归树每层减半,深度正好 lg(n);// 乘 2 是预留两倍余量。一旦递归超过 2*lg(n),// 说明分区持续严重不平衡,立刻判定为病态输入 - 切堆排序。constexprstd::ptrdiff_tlg2(std::ptrdiff_t n){std::ptrdiff_t k0;for(;n!0;n1)k;// 移到 n 的最高位,顺便数位数returnk-1;// 高位置编号 位数 - 1}// ---------------------------------------------------------------// 辅助 2:三点取中,并把中位数交换到 result(队首)// ---------------------------------------------------------------// libstdc 的 __move_median_to_first:// 取 first、mid、last-1 三个元素,把三者中值交换到 result 处。// 目的:// a) 枢轴取中间值,避免取到最小/最大元素而退化成「倾斜分区」;// b) 枢轴就位于队首后,分区可以直接从 first1 开扫;// c) 对已有序/倒序输入的抵抗力大幅提升(第一趟就能切到中位)。templatetypenameRandomIt,typenameCompareRandomItmove_median_to_first(RandomIt result,RandomIt a,RandomIt b,RandomIt c,Compare comp){if(comp(*a,*b)){// 情形一:a bif(comp(*b,*c))// a b c - 中位数 bstd::iter_swap(result,b);elseif(comp(*a,*c))// a c b - 中位数 cstd::iter_swap(result,c);else// c a b - 中位数 astd::iter_swap(result,a);}else{// 情形二:b aif(comp(*a,*c))// b a c - 中位数 astd::iter_swap(result,a);elseif(comp(*b,*c))// b c a - 中位数 cstd::iter_swap(result,c);else// c b a - 中位数 bstd::iter_swap(result,b);}returnresult;// result 即队首,枢轴已就位}// ---------------------------------------------------------------// 辅助 3:未防护线性插入(单元素插入已有序前缀)// ---------------------------------------------------------------// libstdc 的 __unguarded_linear_insert。// 「未防护」 循环里不做「next 是否越过首元素」的边界检查,// 因为它有一个必须被满足的前提:该位置左侧存在一个哨兵元素,// 且哨兵 val。这样 while 必然在越过哨兵之前停下。//// 待插值在此按值快照进局部变量 val:// 插入过程需要把比 val 大的元素逐个右移,val 必须保持恒定基准;// 若以引用形式绑定到容器元素,元素被覆盖时 val 会随引用漂移、// 原值丢失。按值拷贝(与 libstdc 一致)保证基准不变量。templatetypenameRandomIt,typenameComparevoidunguarded_linear_insert(RandomIt last,Compare comp){typenamestd::iterator_traitsRandomIt::value_type valstd::move(*last);// 按值快照待插值RandomIt nextlast;--next;// 指向 last 的前一个已排序元素while(comp(val,*next)){// 凡比 val 大的,整体右移一格*laststd::move(*next);lastnext;--next;}*laststd::move(val);// 找到正确的插入点}// ---------------------------------------------------------------// 插入排序变体 A:带防护(可对任意小数组排序)// ---------------------------------------------------------------// libstdc 的 __insertion_sort:// 进来先特判「新元素比整段最左还小」,这种情况下把整段右移一位、// key 塞到队首;否则才走未防护线性插入——此时已确认 key *first,// 哨兵前提成立,不会越界。templatetypenameRandomIt,typenameComparevoidinsertion_sort(RandomIt first,RandomIt last,Compare comp){if(firstlast)return;// 空区间直接返回for(RandomIt ifirst1;i!last;i){typenamestd::iterator_traitsRandomIt::value_type keystd::move(*i);if(comp(key,*first)){// key 比队首还小std::move_backward(first,i,i1);// [first,i) 整体右移一格*firststd::move(key);// key 落位队首}else{unguarded_linear_insert(i,comp);// 内部自行按值快照}}}// ---------------------------------------------------------------// 插入排序变体 B:完全未防护(不检查哨兵)// ---------------------------------------------------------------// libstdc 的 __unguarded_insertion_sort,只被 final_insertion_sort// 的「第二段」调用。它不特判、不做边界检查,靠的是前提:// 调用者已保证待处理区间左侧已排好序、且该区间每个元素都不小于// 相对的队哨兵(段间全局有序,见 introsort_loop 的切除性质)。templatetypenameRandomIt,typenameComparevoidunguarded_insertion_sort(RandomIt first,RandomIt last,Compare comp){for(RandomIt ifirst;i!last;i)unguarded_linear_insert(i,comp);}// ---------------------------------------------------------------// 分阶段收尾排序:final_insertion_sort// ---------------------------------------------------------------// 内省循环切完所有段后,序列形态是:// 段1(16,乱序) | 段2(16,乱序) | ... | 段k(16,乱序)// 且段与段之间全局有序:段 i 的全部元素 段 i1 的全部元素。// 此时:// 第一步:对最前 kThreshold 个元素做「带防护」插入排序,// 并把这 16 个元素的区间变成后续未防护插入的合法哨兵区;// 第二步:对剩下的元素做「未防护」插入排序(免边界检查)。// 因为段间有序,第二段里的任何元素都不会小到需要越过哨兵区,// 未防护循环必然安全停下。templatetypenameRandomIt,typenameComparevoidfinal_insertion_sort(RandomIt first,RandomIt last,Compare comp){if(last-firstkThreshold){insertion_sort(first,firstkThreshold,comp);// 第一段:带防护unguarded_insertion_sort(firstkThreshold,last,comp);// 第二段:未防护}else{insertion_sort(first,last,comp);// 整段都不大,直接排}}// ---------------------------------------------------------------// 堆排序兜底:partial_sort_heap// ---------------------------------------------------------------// 递归深度超限时调用,等价于 libstdc 的 __partial_sort:// 建堆 堆排序,最坏 O(n log n),且有严格的原地特性。// 它的任务只有一个:把当前 [first,last) 整段彻底排好,// 然后整个内省循环提前结束。templatetypenameRandomIt,typenameComparevoidpartial_sort_heap(RandomIt first,RandomIt last,Compare comp){std::make_heap(first,last,comp);std::sort_heap(first,last,comp);}// ---------------------------------------------------------------// 未防护分区:unguarded_partition// ---------------------------------------------------------------// libstdc 的 __unguarded_partition(快排核心划分)。// 双指针相向:// first:从左向右扫描,停在不小于枢轴的第一个元素;// last :从右向左扫描,停在不大于枢轴的第一个元素;// 两个指针互指一对「放错边」的元素就交换归位。// 返回分界点 cut 满足:// [first,cut) 内所有元素 枢轴,[cut,last) 内所有元素 枢轴,// cut 处恰好是枢轴值的最终落位点。// 之所以叫「未防护」:序列内至少有一个枢轴值打底(见区划调度),// 两个内层 while 保证必停,故无需越界判断。templatetypenameRandomIt,typenameCompareRandomItunguarded_partition(RandomIt first,RandomIt last,RandomIt pivot,Compare comp){while(true){while(comp(*first,*pivot))first;// 向前找 枢轴的元素--last;while(comp(*pivot,*last))--last;// 向后找 枢轴的元素if(!(firstlast))returnfirst;// 指针相遇/交错 - 分区完毕std::iter_swap(first,last);// 交换一对错位元素first;// 关键:前进一格,防原地死循环}}// ---------------------------------------------------------------// 分区调度:取枢轴到队首 - 未防护分区// ---------------------------------------------------------------// libstdc 的 __unguarded_partition_pivot:// (a) 三点取中样本选 first1、mid、last-1。选 first1 而非 first,// 是因为 first 要留给枢轴落位,三点样本应在区间内尽量散布均匀;// (b) move_median_to_first 把中位数换到 first,枢轴就位;// (c) 分区从 first1 开始:first 本身即是枢轴哨兵,// 直接进入未防护双指针分区,返回切分点 cut。templatetypenameRandomIt,typenameCompareRandomItunguarded_partition_pivot(RandomIt first,RandomIt last,Compare comp){RandomIt midfirst(last-first)/2;// 中点move_median_to_first(first,first1,mid,last-1,comp);returnunguarded_partition(first1,last,first,comp);}// ---------------------------------------------------------------// 内省主循环:introsort_loop// ---------------------------------------------------------------// libstdc 的 __introsort_loop:// - 循环条件:区间长度 kThreshold 才细分,否则留给收尾插入排序;// - 深度耗尽:切堆排序兜底并整体返回;// - 每轮:取枢轴 - 分区 - 「递归右半 [cut,last)」,// 左半 [first,cut) 交给外层 while 继续迭代。// 只递归一侧的好处:调用栈深度不因两侧同时递归而翻倍,// 配合 2*lg(n) 深度上限可以稳妥命中堆排序兜底。templatetypenameRandomIt,typenameComparevoidintrosort_loop(RandomIt first,RandomIt last,std::ptrdiff_t depth_limit,Compare comp){while(last-firstkThreshold){// 段还太大,需要继续切if(depth_limit0){// 递归太深 - 病态输入partial_sort_heap(first,last,comp);// 整段堆排序兜底return;// 该段已彻底排好,收工}--depth_limit;// 消耗一层递归额度RandomIt cutunguarded_partition_pivot(first,last,comp);introsort_loop(cut,last,depth_limit,comp);// 递归处理右半(含枢轴)lastcut;// 左半交给下一次循环迭代}// 退出 while 时本段长度 kThreshold,留给 final_insertion_sort 收尾}// ---------------------------------------------------------------// 统一入口:sort(唯一版本,无重载)// ---------------------------------------------------------------// 流程 introsort_loop(先切段) - final_insertion_sort(收尾排序)。// 深度上限 2*lg(n),每次进入递归前都会 -1,// 即默认给快排预留「两倍最优深度」的犯错空间。//// Compare 用默认模板参数 默认函数实参,使同一函数既能以// sort(first, last) 两参调用(默认 std::less 升序),// 也能以// sort(first, last, 自定义比较器) 三参调用;// 不存在第二个 sort 重载,也就杜绝了与 std::sort 的名字查找歧义。templatetypenameRandomIt,typenameComparestd::lesstypenamestd::iterator_traitsRandomIt::value_typevoidsort(RandomIt first,RandomIt last,Compare compCompare()){if(firstlast)return;// 空区间conststd::ptrdiff_t nlast-first;if(nkThreshold){introsort_loop(first,last,2*lg2(n),comp);}final_insertion_sort(first,last,comp);}}// namespace my_introsort// // main:用例覆盖 正常 / 空 / 单元素 / 已有序 / 逆序 / 全重复 /// 大量重复小值域 / 随机对照 / 自定义比较器// intmain(){// 1) 常规乱序std::vectorintv1{5,3,8,1,9,2,7,4,6};my_introsort::sort(v1.begin(),v1.end());assert(std::is_sorted(v1.begin(),v1.end()));// 2) 空区间std::vectorintempty;my_introsort::sort(empty.begin(),empty.end());assert(std::is_sorted(empty.begin(),empty.end()));// 3) 单元素std::vectorintone{42};my_introsort::sort(one.begin(),one.end());assert(std::is_sorted(one.begin(),one.end()));// 4) 病态输入 A:已有序(传统快排的最坏情形)std::vectorinta;for(inti0;i4096;i)a.push_back(i);my_introsort::sort(a.begin(),a.end());assert(std::is_sorted(a.begin(),a.end()));// 5) 病态输入 B:完全逆序std::vectorintb(a.rbegin(),a.rend());my_introsort::sort(b.begin(),b.end());assert(std::is_sorted(b.begin(),b.end()));// 6) 病态输入 C:全部相等(大量重复,考验分区稳定性与死循环防护)std::vectorintc(100000,7);my_introsort::sort(c.begin(),c.end());assert(std::is_sorted(c.begin(),c.end()));// 7) 大量重复 小值域(重元素排列的典型压力形态)std::mt19937rng2(7);std::vectorintg(50000),h;for(intx:g)xstatic_castint(rng2()%64);hg;std::sort(h.begin(),h.end());// 基准答案my_introsort::sort(g.begin(),g.end());assert(gh);// 8) 随机 10000 个,与 std::sort 结果逐元素对照std::mt19937rng(42);std::vectorintd(10000),e;for(intx:d)xstatic_castint(rng()%100000);ed;std::sort(e.begin(),e.end());// 基准答案my_introsort::sort(d.begin(),d.end());assert(de);// 9) 自定义比较器:降序std::vectorintf{1,9,2,8,3,7,0,5};my_introsort::sort(f.begin(),f.end(),std::greaterint());assert(std::is_sorted(f.begin(),f.end(),std::greaterint()));std::puts(all tests passed);return0;}