內觀排序（introsort)是快速排序的一種改進形式，即C++中的std::sort()。
基本介紹
- 中文名：內觀排序
- 外文名：introsort
- 屬性：快速排序的一種改進形式
- 學科：C++
簡介
在實踐中，快速排序的速度很快的，不足的地方是在某些情況下，速度會很慢。原因是切分原素選取不合理，使得切分出來的兩個問題大小不對稱，子問題太多，深度太深。一個可行的改進是，選三個元素，然後取中間的一個作為切分元素，這樣效果會好些，但是仍然會有一些極端的情況會使得算法退化為平方。只要這三個元素是可以預計的，都能設計出讓算法退化的輸入。另一個改進方案是，選一個隨機數。假設隨機數發生器比較隨機。但是只產生一個隨機數，切分出來的效果還是不會很好，多產生幾個隨機數，再選中間數，效果會好些，只是產生隨機數的過程本身就耗時，所以不能產生太多。
有些算法不用隨機數，也能確保算法不會退化到平方。但是在實踐中，這些算法速度很慢。
內觀排序，即把快速排序跟堆排序結合起來。堆排序是很穩定的，不會退化，只是一般情況下比較慢。在快速排序t算法出現退化的情況下，再調用堆排序。問題是怎么判斷退化。一種簡單的方案是，當深度超過某值的時候，根據經驗，這個值可以設為2*lgN。直接調用堆排序對切分後的子問題進行排序。
這個算法在平均情況下，跟快速排序差不多，在最壞情況下，比快速排序要快一個數量級。
介紹一下快速排序里在退化到n^2的情況下，怎樣避免堆疊溢出。每次切分後，會產生兩個子問題，對較小的子問題作遞歸，較大的子問題則替換掉原來的問題，然後繼續循環，不用遞歸調用。這樣雖然子問題還是很多，但是遞歸的深度卻較小。
