std::sort的底層是快速排序嗎？可能遠(yuǎn)不止如此

C語(yǔ)言與CPP編程

請(qǐng)介紹下C++中的std::sort算法？
回答重點(diǎn)
std::sort 非常高效，它不單純是快速排序，而是使用了一種名為 introspective sort（內(nèi)省排序）的算法。
內(nèi)省排序是快速排序、堆排序和插入排序的結(jié)合體，它結(jié)合這些算法優(yōu)點(diǎn)的同時(shí)避免它們的缺點(diǎn)，特別是快速排序在最壞情況下的性能下降問(wèn)題。
注意：本題介紹，僅限于GCC的源碼實(shí)現(xiàn)。
擴(kuò)展知識(shí)快速排序：內(nèi)省排序首先使用快速排序算法。利用快速排序分而治之的特點(diǎn)，通過(guò)選取一個(gè)pivot元素，將數(shù)組分為兩個(gè)子數(shù)組，一個(gè)包含小于pivot的元素，另一個(gè)包含大于pivot的元素，然后遞歸地對(duì)這兩個(gè)子數(shù)組進(jìn)行快速排序�？焖倥判蛟谄骄�情況下非常高效，時(shí)間復(fù)雜度為 O(n log n)。

/// This is a helper function for the sort routine.template typename _RandomAccessIterator, typename _Size, typename _Compare>_GLIBCXX20_CONSTEXPR void__introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,                 _Size __depth_limit, _Compare __comp) {  while (__last - __first > int(_S_threshold)) {    if (__depth_limit == 0) {      std::__partial_sort(__first, __last, __last, __comp);      return;    }    --__depth_limit;    _RandomAccessIterator __cut =        std::__unguarded_partition_pivot(__first, __last, __comp);    std::__introsort_loop(__cut, __last, __depth_limit, __comp);    __last = __cut;  }}
// sort
template typename _RandomAccessIterator, typename _Compare>_GLIBCXX20_CONSTEXPR inline void __sort(_RandomAccessIterator __first,                                        _RandomAccessIterator __last,                                        _Compare __comp) {  if (__first != __last) {    std::__introsort_loop(__first, __last, std::__lg(__last - __first) * 2,                          __comp);    std::__final_insertion_sort(__first, __last, __comp);  }}內(nèi)省排序：通過(guò)限制快速排序遞歸深度，避免其最壞情況的性能問(wèn)題。遞歸深度的限制基于輸入數(shù)組的大小，通常是對(duì)數(shù)組長(zhǎng)度取對(duì)數(shù)然后乘以一個(gè)常數(shù)（在 GCC 實(shí)現(xiàn)中是 2 * log(len)）。如果排序過(guò)程中遞歸深度超過(guò)了這個(gè)限制，算法會(huì)切換到堆排序。

/// This is a helper function for the sort routine.template typename _RandomAccessIterator, typename _Size, typename _Compare>_GLIBCXX20_CONSTEXPR void__introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,                 _Size __depth_limit, _Compare __comp) {  while (__last - __first > int(_S_threshold)) {    if (__depth_limit == 0) {      std::__partial_sort(__first, __last, __last, __comp);      return;    }    --__depth_limit;    _RandomAccessIterator __cut =        std::__unguarded_partition_pivot(__first, __last, __comp);    std::__introsort_loop(__cut, __last, __depth_limit, __comp);    __last = __cut;  }}
// sort
template typename _RandomAccessIterator, typename _Compare>_GLIBCXX20_CONSTEXPR inline void __sort(_RandomAccessIterator __first,                                        _RandomAccessIterator __last,                                        _Compare __comp) {  if (__first != __last) {    std::__introsort_loop(__first, __last, std::__lg(__last - __first) * 2,                          __comp);    std::__final_insertion_sort(__first, __last, __comp);  }}堆排序：當(dāng)快速排序的遞歸深度超過(guò)限制時(shí)，內(nèi)省排序會(huì)切換到堆排序，保證最壞情況下的時(shí)間復(fù)雜度為 O(n log n)。堆排序不依賴于數(shù)據(jù)的初始排列，因此它的性能無(wú)論在最好、平均和最壞情況下都是穩(wěn)定的。

/// This is a helper function for the sort routine.template typename _RandomAccessIterator, typename _Size, typename _Compare>_GLIBCXX20_CONSTEXPR void__introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,                 _Size __depth_limit, _Compare __comp) {  while (__last - __first > int(_S_threshold)) {    if (__depth_limit == 0) {      std::__partial_sort(__first, __last, __last, __comp);      return;    }    --__depth_limit;    _RandomAccessIterator __cut =        std::__unguarded_partition_pivot(__first, __last, __comp);    std::__introsort_loop(__cut, __last, __depth_limit, __comp);    __last = __cut;  }}插入排序：最后，當(dāng)數(shù)組的大小減小到一定程度時(shí)，內(nèi)省排序會(huì)使用插入排序來(lái)處理小數(shù)組。插入排序在小數(shù)組上非常高效，盡管它的平均和最壞情況時(shí)間復(fù)雜度為 O(n^2)，但在數(shù)據(jù)量小的情況下，這種復(fù)雜度不是問(wèn)題。此外，插入排序是穩(wěn)定的，可以保持等值元素的相對(duì)順序。

/// This is a helper function for the sort routine.template typename _RandomAccessIterator, typename _Compare>_GLIBCXX20_CONSTEXPR void __final_insertion_sort(_RandomAccessIterator __first,                                                 _RandomAccessIterator __last,                                                 _Compare __comp) {  if (__last - __first > int(_S_threshold)) {    std::__insertion_sort(__first, __first + int(_S_threshold), __comp);    std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,                                    __comp);  } else    std::__insertion_sort(__first, __last, __comp);}——EOF——你好，我是飛宇。日常分享C/C++、計(jì)算機(jī)學(xué)習(xí)經(jīng)驗(yàn)、工作體會(huì)，歡迎點(diǎn)擊此處查看我以前的學(xué)習(xí)筆記&經(jīng)驗(yàn)&分享的資源。
我組建了一些社群一起交流，群里有大牛也有小白，如果你有意可以一起進(jìn)群交流。

歡迎你添加我的微信，我拉你進(jìn)技術(shù)交流群。此外，我也會(huì)經(jīng)常在微信上分享一些計(jì)算機(jī)學(xué)習(xí)經(jīng)驗(yàn)以及工作體驗(yàn)，還有一些內(nèi)推機(jī)會(huì)。


加個(gè)微信，打開另一扇窗
↓推薦關(guān)注↓
感謝你的分享，點(diǎn)贊，在看三連