内省排序 内省排序英語Introsort是由大衛穆塞爾在年设计的排序算法这个排序算法首先从快速排序开始当递归深度超过一定深度深度为排序元素数量的对数值后转为堆排序采用这个方法内省排序既能在常规数据集上实现快速排序的高性能又能在最坏情况下仍保持 O  n log  n  displaystyle Onlog n 的时间复杂度由于这两种算法都属于比较排序算法所以内省排序也是一个比较排序算法 在快速排序算法中一个关键操作就是选择基准点Pivot元素将被此基准点分开成两部分最简单的基准点选择算法是使用第一个或者最后一个元素但这在排列已部分有序的序列上性能很糟尼克劳斯维尔特为此设计了一个快速排序的变体使用处于中间的元素来防止在某些特定序列上性能退化为 O  n   displaystyle On 的状况这个基准中位数选择算法从序列的第一中间和最后一个元素取得中位数来作为基准虽然这个算法在现实世界的数据上性能表现良好但经过精心设计的破解序列仍能大幅降低此变体算法的性能这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务DoS攻击的潜在可能性 穆塞爾研究指出在针对基准中位数选择算法设计的个元素的破解序列上内省排序的运行时间是这种基准快速排序的  在穆塞爾的算法中最终较小范围内数据的排序由羅伯特塞奇威克提出的小数据排序算法完成 在年月SGI的C标准模板库的stlalgoh 页面存档备份存于互联网档案馆中的不稳定排序算法采用了穆塞爾的内省排序算法在此实现中切换到插入排序的数据量阈值为个