快速排序的独特之处在于，其速度取决于选择的基准值。在讨论快速排序的运行时间前，我们再来看看最常见的大O运行时间。

上述图表中的时间是基于每秒执行10次操作计算得到的。这些数据并不准确，这里提供它们只是想让你对这些运行时间的差别有大致认识。实际上，计算机每秒执行的操作远不止10次。

对于每种运行时间，本书还列出了相关的算法。来看看第2章介绍的选择排序，其运行时间为O(n2)，速度非常慢。

还有一种名为合并排序（merge sort）的排序算法，其运行时间为O(n log n)，比选择排序快得多！快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。

与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为O(n log n)。你可能会有如下疑问。

• 这里说的最糟情况和平均情况是什么意思呢？
• 若快速排序在平均情况下的运行时间为O(n log n)，而合并排序的运行时间总是O(n log n)，为何不使用合并排序？它不是更快吗？