內省排序
 |
| 內省排序 | |
|---|---|
| 概況 | |
| 類別 | 排序算法 |
| 資料結構 | 數組 |
| 複雜度 | |
| 平均時間複雜度 | |
| 最壞時間複雜度 | |
| 相關變量的定義 | |
內省排序（英語：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.