基本介紹
- 中文名：內省排序
- 外文名：Introsort
- 領域：計算機科學
簡介,排序算法,排序算法列表,穩定的排序,不穩定的排序,不實用的排序,
簡介
內省排序（英語：Introsort）是由David Musser在1997年設計的排序算法。這個排序算法首先從快速排序開始，當遞歸深度超過一定深度（深度為排序元素數量的對數值）後轉為堆排序。採用這個方法，內省排序既能在常規數據集上實現快速排序的高性能，又能在最壞情況下仍保持
的時間複雜度。由於這兩種算法都屬於比較排序算法，所以內省排序也是一個比較排序算法。
在快速排序算法中，一個關鍵操作就是選擇基準點（Pivot）：元素將被此基準點分開成兩部分。最簡單的基準點選擇算法是使用第一個或者最後一個元素，但這在排列已部分有序的序列上性能很糟。Niklaus Wirth為此設計了一個快速排序的變體，使用處於中間的元素來防止在某些特定序列上性能退化為{\displaystyle O(n^{2})}的狀況。這個3基準中位數選擇算法從序列的第一，中間和最後一個元素獲取中位數來作為基準，雖然這個算法在現實世界的數據上性能表現良好，但經過精心設計的序列仍能大幅降低此算法性能。這樣就有攻擊者精心設計序列傳送到網際網路伺服器以進行拒絕服務（DoS）攻擊的潛在可能性。
Musser研究指出，在為3基準中位數選擇算法精心設計的100,000個元素序列上，introsort的運行時間是快速排序的1 / 200。在Musser的算法中，最終較小範圍內數據的排序由Sedgewick提出的小數據排序算法完成。
排序算法
在計算機科學與數學中，一個排序算法（英語：Sorting algorithm）是一種能將一串數據依照特定排序方式進行排列的一種算法。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法（例如搜尋算法與合併算法）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字數據以及產生人類可讀的輸出結果。基本上，排序算法的輸出必須遵守下列兩個原則：
- 輸出結果為遞增序列（遞增是針對所需的排序順序而言）；
- 輸出結果是原輸入的一種排列、或是重組。
雖然排序算法是一個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。舉例而言，冒泡排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題，有用的新算法仍在不斷的被發明。
