内省排序
 |
| 内省排序 | |
|---|---|
| 概况 | |
| 类别 | 排序算法 |
| 数据结构 | 数组 |
| 复杂度 | |
| 平均时间复杂度 | |
| 最坏时间复杂度 | |
| 相关变量的定义 | |
内省排序（英语：Introsort）是由大卫·穆塞尔在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。
在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。最简单的基准点击择算法是使用第一个或者最后一个元素，但这在排列已部分有序的序列上性能很糟。尼克劳斯·维尔特为此设计了一个快速排序的变体，使用处于中间的元素来防止在某些特测序列上性能退化为的状况。这个3基准中位数选择算法从序列的第一，中间和最后一个元素获取中位数来作为基准，虽然这个算法在现实世界的数据上性能表现良好，但经过精心设计的“破解序列”仍能大幅降低此变体算法的性能。这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务（DoS）攻击的潜在可能性。
穆塞尔研究指出，在针对3基准中位数选择算法设计的100,000个元素的“破解序列”上，内省排序的运行时间是这种3基准快速排序的1 / 200。在穆塞尔的算法中，最终较小范围内数据的排序由罗伯特·塞奇威克提出的小数据排序算法完成。
在2000年6月，SGI的C++标准模板库的stl_algo.h （页面存档备份，存于互联网档案馆）中的不稳定排序算法采用了穆塞尔的内省排序算法。在此实现中，切换到插入排序的数据量阈值为16个。
参考文献
[编辑]- Musser, David. Introspective Sorting and Selection Algorithms. Software: Practice and Experience (Wiley). 1997, 27 (8): 983–993 [2011-08-13]. （原始内容存档于2012-07-16）.
- Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.
外部链接
[编辑]- "A guide to Introsort" Paper created over the course of a student research project by Ralph Unden. Contains a complete implementation in Java.