Quicksort

释义 Definition

快速排序：一种常用的比较排序算法，通过选择一个“枢轴”（pivot），把序列按“小于枢轴”和“大于枢轴”分区（partition），再对两个子序列递归排序。平均时间复杂度通常为 **O(n log n)**，但在某些输入下最坏可达 **O(n²)**。

发音 Pronunciation (IPA)

/ˈkwɪk.sɔːrt/

例句 Examples

Quicksort is fast on average.
快速排序在平均情况下很快。

To improve performance, the implementation chooses a random pivot before applying quicksort to large arrays.
为了提升性能，这个实现会在对大型数组进行快速排序之前随机选择枢轴。

词源 Etymology

quicksort 由 quick（快速的）+ sort（排序）构成，是计算机科学中对该算法的命名；该算法由英国计算机科学家 Tony Hoare 在 20 世纪 60 年代提出并推广，因此得名强调“快速的排序方法”。

相关词 Related Words

• Algorithm
• Big-O Notation
• Divide and Conquer
• Heap Sort
• Merge Sort
• Partition
• Pivot
• Recursion
• Sorting

文学与名著 Literary Works

• Quicksort（C. A. R. Hoare，1961/1962 相关论文与发表版本中讨论该算法）
• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）
• Introduction to Algorithms（Thomas H. Cormen 等，常称 CLRS）
• Algorithms（Robert Sedgewick，含快速排序的讲解与实现思路）