Introsort

释义 Definition

Introsort（内省排序）是一种混合排序算法：通常先使用快速排序（Quicksort），在递归深度过大、可能退化为最坏情况时，自动切换为堆排序（Heapsort）以保证时间复杂度；并常在小规模子数组上使用插入排序（Insertion sort）提升常数效率。它常见于许多语言/库的通用排序实现（如 C++ 的 std::sort）。

例句 Examples

Introsort is fast in practice and avoids quicksort’s worst-case slowdown.
Introsort 在实践中很快，并能避免快速排序在最坏情况下的性能骤降。

Many standard libraries implement their default sort using introsort, switching to heapsort when recursion gets too deep.
许多标准库用内省排序实现默认排序：当递归过深时会切换到堆排序。

发音 Pronunciation (IPA)

/ˈɪntrəˌsɔːrt/

词源 Etymology

Introsort 是 introspective sort（“内省的排序”）的缩写/合成词：*intro-*（向内、内省）+ sort（排序）。含义是算法会“自我检查”运行状态（如递归深度），在检测到可能变慢时改变策略。该算法由 David R. Musser 在 1990 年代提出并推广。

相关词 Related Words

• Quicksort
• Heapsort
• Insertion
• Partition
• Recursion
• Complexity
• Algorithm
• Std::sort

文学与著作中的用例 Literary / Notable Works

• David R. Musser：《Introspective Sorting and Selection Algorithms》（论文/技术报告，1997）——提出并系统描述 introsort 的经典来源。
• Nicolai M. Josuttis：《The C++ Standard Library》——在讲解 std::sort 及其实现策略时常提及 introsort。
• Bjarne Stroustrup：《The C++ Programming Language》及相关 C++ 标准库材料——讨论通用排序（如 std::sort）时常与 introsort 关联。