经典内省排序 Introsort —— David R. Musser, 1997

// // 经典内省排序 Introsort —— David R. Musser, 1997// 论文:Introspective Sorting and Selection Algorithms,// Software: Practice and Experience, 27(8):983-993, 1997.// 单文件完整版,含 main 用例。编译运行:// g -stdc17 -Wall -Wextra main.cpp -o main ./main// 预期输出:all tests passed// // 算法三组件(1997 原始结构,无 std::sort 增强项):// 1. 快速排序 —— 主流路径,median-of-three 选枢轴 单向分区;// 2. 堆排序(自实现) —— 递归深度超过 2*lg(n) 时整段切换,// 把最坏复杂度锁死在 O(n log n);// 3. 插入排序 —— 区间长度 16 时收尾(小数组上常数极小)。// 深度计数是「内省」的本体:快排每层递归把区间减半,理想深度 lg(n),// 超过 2 倍余量即判定输入病态(有序/逆序/大量重复),立刻降级堆排。//// 命名注意:命名空间内的非限定调用(如 partition/introsort)可能被 ADL// (实参关联命名空间含 std 时把 std::partition 等拉进候选集)引入歧义;// 凡与 std 同名的内部函数,调用点一律写全限定 classic_introsort::xxx。// #includealgorithm#includecassert#includecstdio#includefunctional#includeiterator#includerandom#includeutility#includevectornamespaceclassic_introsort{// 阈值:区间长度不超过 16 时,插入排序比快排便宜staticconstexprstd::ptrdiff_t kThreshold16;// ---------------------------------------------------------------// 辅助 1:log2 下取整(用于计算递归深度上限)// ---------------------------------------------------------------// 返回最大的 k,使 2^k n,即 n 的二进制最高位序号。// 深度上限取 2 * lg2(n):理想平衡快排递归深度恰为 lg(n),// 乘 2 等于给快排两倍「犯错余量」,超过即判定病态。std::ptrdiff_tlg2(std::ptrdiff_t n){std::ptrdiff_t k0;for(;n!0;n1)k;// 反复右移直至归零,统计位数returnk-1;// 最高位序号 位数 - 1}// ---------------------------------------------------------------// 组件 1:插入排序(对小区间收尾)// ---------------------------------------------------------------// 稳定、原地、对近乎有序序列接近 O(n)。// 从第 2 个元素起,每个元素向前找到正确位置并插入// (比它大的元素整体右移一格,key 落位)。// 必须守卫空区间:first last 时 first1 已越界,// 直接解引用 *i 会段错误(经典版本遗漏点,已补)。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);// 取出待插值(值拷贝,基准恒定)RandomIt ji;while(j!firstcomp(key,*(j-1))){*jstd::move(*(j-1));// 比 key 大的逐个右移--j;}*jstd::move(key);// key 落到正确位置}}// ---------------------------------------------------------------// 组件 2:堆排序(自实现,深度超限时的兜底)// ---------------------------------------------------------------// 二叉最大堆(按 comp 比较)下沉操作:// root 与其左右子(2*root1 / 2*root2)中较大者比较,// 若不满足堆序则交换并继续下沉,保证子树恢复堆性质。templatetypenameRandomIt,typenameComparevoidsift_down(RandomIt first,std::ptrdiff_t n,std::ptrdiff_t root,Compare comp){while(true){std::ptrdiff_t child2*root1;// 左子下标if(childn)return;// 越界 - 已是叶子,下沉完成if(child1ncomp(first[child],first[child1])){child;// 取左右子中「较大」者}if(!comp(first[root],first[child]))return;// 父已不小于子,完成std::iter_swap(firstroot,firstchild);// 父子交换rootchild;// 继续向下调整}}// 堆排序:先建堆(自底向上逐结点下沉),再反复把堆顶// (全局最大)换到末尾,堆规模减一后重新下沉堆顶。// 最坏 O(n log n),空间 O(1)。templatetypenameRandomIt,typenameComparevoidheapsort(RandomIt first,RandomIt last,Compare comp){conststd::ptrdiff_t nlast-first;for(std::ptrdiff_t in/2-1;i0;--i)// 建堆:最后一个非叶起sift_down(first,n,i,comp);for(std::ptrdiff_t in-1;i0;--i){// 逐元素取出堆顶std::iter_swap(first,firsti);// 堆顶(最大)归位末尾sift_down(first,i,0,comp);// 剩余部分重新调整}}// ---------------------------------------------------------------// 辅助 2:三点取中,返回中位数的迭代器(经典选枢轴法)// ---------------------------------------------------------------// 取 first、mid、last-1 三个元素的中位数作枢轴候选:// 避免取到区间最小/最大元素而退化成「倾斜分区」,// 对已有序/逆序输入第一趟就能切到中位。templatetypenameRandomIt,typenameCompareRandomItmedian_of_three(RandomIt a,RandomIt b,RandomIt c,Compare comp){if(comp(*a,*b)){// a bif(comp(*b,*c))returnb;// a b c - 中位 breturncomp(*a,*c)?c:a;// c b,则中位为 c 或 a}else{// b aif(comp(*a,*c))returna;// b a c - 中位 areturncomp(*b,*c)?c:b;// c a,则中位为 c 或 b}}// ---------------------------------------------------------------// 组件 1 核心:单向分区(Lomuto 式)// ---------------------------------------------------------------// 选三点中位作枢轴,换到区间末尾;从左扫描,// 凡 枢轴的元素依次换到前部(store 指针标记边界);// 最后把枢轴放回分界处。// 返回 cut:枢轴最终位置,满足// [first,cut) 全部 枢轴, [cut1,last) 全部 枢轴。// 调用前提:last - first kThreshold 0,故 last-1 恒有效。templatetypenameRandomIt,typenameCompareRandomItpartition(RandomIt first,RandomIt last,Compare comp){RandomIt midfirst(last-first)/2;// 中点RandomIt pivot_itmedian_of_three(first,mid,last-1,comp);std::iter_swap(pivot_it,last-1);// 枢轴挪到末尾typenamestd::iterator_traitsRandomIt::value_type pivotstd::move(*(last-1));// 值拷贝枢轴(基准恒定)RandomIt storefirst;// 小元素放置区边界for(RandomIt itfirst;it!last-1;it){if(comp(*it,pivot)){// 比枢轴小 - 归左区std::iter_swap(it,store);store;}}std::iter_swap(store,last-1);// 枢轴放回分界处returnstore;// 枢轴位置}// ---------------------------------------------------------------// 组件 1 主递归:introsort(经典 1997 结构)// ---------------------------------------------------------------// 循环条件:区间长度 阈值才细分,否则交给插入排序收尾。// 每轮:// 1) 深度耗尽 - 整段切堆排序,该段彻底排好,立即返回;// 2) 消耗一层深度额度;// 3) 分区得到枢轴位置 cut;// 4) 递归处理右半 [cut1, last);// 5) 左半 [first, cut] 交给外层 while 继续迭代(半迭代省栈)。// 与 std 同名的调用一律写全限定,避免 ADL 引入候选歧义。templatetypenameRandomIt,typenameComparevoidintro_sort_impl(RandomIt first,RandomIt last,std::ptrdiff_t depth,Compare comp){while(last-firstkThreshold){// 段还太大,需要继续切if(depth0){// 递归太深 - 病态输入heapsort(first,last,comp);// 整段堆排序兜底return;// 该段已彻底排好}--depth;// 消耗一层递归额度RandomIt cutclassic_introsort::partition(first,last,comp);classic_introsort::intro_sort_impl(cut1,last,depth,comp);// 递归右半lastcut;// 左半(含枢轴)交给下次循环}// 退出 while 时本段 阈值,留待收尾插入排序}// ---------------------------------------------------------------// 统一入口:introsort// ---------------------------------------------------------------// 深度上限 2 * lg2(n):每次进入递归前都会 -1,// 即默认给快排预留「两倍最优深度」的犯错空间。// 流程 intro_sort_impl(先切段) - insertion_sort(收尾)。templatetypenameRandomIt,typenameComparevoidintrosort(RandomIt first,RandomIt last,Compare comp){conststd::ptrdiff_t nlast-first;if(nkThreshold){intro_sort_impl(first,last,2*lg2(n),comp);}insertion_sort(first,last,comp);}// 无比较器重载:默认升序(std::less)templatetypenameRandomItvoidintrosort(RandomIt first,RandomIt last){classic_introsort::introsort(first,last,std::lesstypenamestd::iterator_traitsRandomIt::value_type());}}// namespace classic_introsort// // main:用例覆盖 正常 / 空 / 单元素 / 已有序 / 逆序 / 全重复 /// 大量重复小值域 / 随机对照 / 自定义比较器// intmain(){// 1) 常规乱序std::vectorintv1{5,3,8,1,9,2,7,4,6};classic_introsort::introsort(v1.begin(),v1.end());assert(std::is_sorted(v1.begin(),v1.end()));// 2) 空区间(曾触发段错误:insertion_sort 空区间越界,已修复)std::vectorintempty;classic_introsort::introsort(empty.begin(),empty.end());assert(std::is_sorted(empty.begin(),empty.end()));// 3) 单元素std::vectorintone{42};classic_introsort::introsort(one.begin(),one.end());assert(std::is_sorted(one.begin(),one.end()));// 4) 病态输入 A:已有序(传统快排的最坏情形)std::vectorinta;for(inti0;i4096;i)a.push_back(i);classic_introsort::introsort(a.begin(),a.end());assert(std::is_sorted(a.begin(),a.end()));// 5) 病态输入 B:完全逆序std::vectorintb(a.rbegin(),a.rend());classic_introsort::introsort(b.begin(),b.end());assert(std::is_sorted(b.begin(),b.end()));// 6) 病态输入 C:全部相等(大量重复,考验分区稳定性与死循环防护)std::vectorintc(100000,7);classic_introsort::introsort(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());// 基准答案classic_introsort::introsort(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());// 基准答案classic_introsort::introsort(d.begin(),d.end());assert(de);// 9) 自定义比较器:降序std::vectorintf{1,9,2,8,3,7,0,5};classic_introsort::introsort(f.begin(),f.end(),std::greaterint());assert(std::is_sorted(f.begin(),f.end(),std::greaterint()));std::puts(all tests passed);return0;}