查看“︁内省排序”︁的源代码

{{no footnotes|time=2015-01-18T17:46:11+00:00}}
{{NoteTA
|G1 = IT
}}
{{Infobox Algorithm
|class=[[排序算法]]
|image=
|caption=
|data=[[数组]]
|time=<math>O(n\log n)</math>
|average-time= <math>O(n\log n)</math> 
|space=
|optimal=
}} 
'''内省排序'''（{{lang-en|Introsort}}）是由[[大衛·穆塞爾]]在1997年设计的[[排序算法]]。这个排序算法首先从[[快速排序]]开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为[[堆排序]]。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持<math>O(n\log n)</math>的[[时间复杂度]]。由于这两种算法都属于[[比较排序]]算法，所以内省排序也是一个比较排序算法。

在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。最简单的基准点选择算法是使用第一个或者最后一个元素，但这在排列已部分有序的序列上性能很糟。[[尼克劳斯·维尔特]]为此设计了一个快速排序的变体，使用处于中间的元素来防止在某些特定序列上性能退化为<math>O(n^2)</math>的状况。这个3基准中位数选择算法从序列的第一，中间和最后一个元素取得中位数来作为基准，虽然这个算法在现实世界的数据上性能表现良好，但经过精心设计的“破解序列”仍能大幅降低此变体算法的性能。这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务（DoS）攻击的潜在可能性。

穆塞爾研究指出，在针对3基准中位数选择算法设计的100,000个元素的“破解序列”上，内省排序的运行时间是这种3基准快速排序的1 / 200。在穆塞爾的算法中，最终较小范围内数据的排序由[[羅伯特·塞奇威克]]提出的小数据排序算法完成。

在2000年6月，[[硅谷图形公司|SGI]]的C++[[标准模板库]]的[http://www.sgi.com/tech/stl/stl_algo.h stl_algo.h] {{Wayback|url=http://www.sgi.com/tech/stl/stl_algo.h |date=20171223121218 }}中的不稳定排序算法采用了穆塞爾的内省排序算法。在此实现中，切换到插入排序的数据量阈值为16个。

==参考文献==
* {{cite journal
|last=Musser
|first=David
|title=Introspective Sorting and Selection Algorithms
|url=http://www.cs.rpi.edu/~musser/gp/introsort.ps
|journal=Software: Practice and Experience
|volume=27
|issue=8
|publisher=Wiley
|year=1997
|pages=983–993
|author=
|access-date=2011-08-13
|archive-url=https://web.archive.org/web/20120716202050/http://www.cs.rpi.edu/~musser/gp/introsort.ps
|archive-date=2012-07-16
|dead-url=yes
}}

* Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.

==外部链接==
* [https://web.archive.org/web/20110825150145/http://ralphunden.net/?q=a-guide-to-introsort "A guide to Introsort"] Paper created over the course of a student research project by Ralph Unden. Contains a complete implementation in Java.

{{排序算法表}}
{{算法}}
[[Category:排序算法]]