內省排序 |
---|
|
類別 | 排序演算法 |
---|
資料結構 | 陣列 |
---|
|
平均時間複雜度 | ![{\displaystyle O(n\log n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1) |
---|
最壞時間複雜度 | ![{\displaystyle O(n\log n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1) |
---|
|
內省排序(英語:Introsort)是由大衛·穆塞爾在1997年設計的排序演算法。這個排序演算法首先從快速排序開始,當遞歸深度超過一定深度(深度為排序元素數量的對數值)後轉為堆積排序。採用這個方法,內省排序既能在常規數據集上實現快速排序的高效能,又能在最壞情況下仍保持
的時間複雜度。由於這兩種演算法都屬於比較排序演算法,所以內省排序也是一個比較排序演算法。
在快速排序演算法中,一個關鍵操作就是選擇基準點(Pivot):元素將被此基準點分開成兩部分。最簡單的基準點擊擇演算法是使用第一個或者最後一個元素,但這在排列已部分有序的序列上效能很糟。尼克勞斯·維爾特為此設計了一個快速排序的變體,使用處於中間的元素來防止在某些特定序列上效能退化為
的狀況。這個3基準中位數選擇演算法從序列的第一,中間和最後一個元素取得中位數來作為基準,雖然這個演算法在現實世界的數據上效能表現良好,但經過精心設計的「破解序列」仍能大幅降低此變體演算法的效能。這樣就有攻擊者精心設計序列傳送到互聯網伺服器以進行阻斷服務(DoS)攻擊的潛在可能性。
穆塞爾研究指出,在針對3基準中位數選擇演算法設計的100,000個元素的「破解序列」上,內省排序的執行時間是這種3基準快速排序的1 / 200。在穆塞爾的演算法中,最終較小範圍內數據的排序由羅伯特·塞奇威克提出的小數據排序演算法完成。
在2000年6月,SGI的C++標準模板庫的stl_algo.h (頁面存檔備份,存於互聯網檔案館)中的不穩定排序演算法採用了穆塞爾的內省排序演算法。在此實現中,切換到插入排序的數據量閾值為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.
|
---|
| 理論 | |
---|
| 交換排序 | |
---|
| 選擇排序 | |
---|
| 插入排序 | |
---|
| 合併排序 | |
---|
| 分佈排序 | |
---|
| 並行排序 | |
---|
| 混合排序 | |
---|
| 其他 | |
---|
|