2.3 快速排序
Robert Sedgewick Kevin Wayne
本节的主题是快速排序,它可能是应用最广泛的排序算法了。快速排序流行的原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。快速排序引人注目的特点包括它是原地排序(只需要一个很小的辅助栈),且将长度为
的数组排序所需的时间和
成正比。我们已经学习过的排序算法都无法将这两个优点结合起来。另外,快速排序的内循环比大多数排序算法都要短小,这意味着它无论是在理论上还是在实际中都要更快。它的主要缺点是非常脆弱,在实现时要非常小心才能避免低劣的性能。已经有无数例子显示许多种错误都能致使它在实际中的性能只有平方级别。幸好我们将会看到,由这些错误中学到的教训也大大改进了快速排序算法,使它的应用更加广泛。
![](https://static001.geekbang.org/files/resource/ebook/100010/image00798.gif)
![](https://static001.geekbang.org/files/resource/ebook/100010/image00960.gif)
2.3.1 基本算法
快速排序是一种分治的排序算法。它将一个数组分成两个子数组,将两部分独立地排序。快速排序和归并排序是互补的:归并排序将数组分成两个子数组分别排序,并将有序的子数组归并以将整个数组排序;而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中,递归调用发生在处理整个数组之前;在第二种情况中,递归调用发生在处理整个数组之后。在归并排序中,一个数组被等分为两半;在快速排序中,切分(partition)的位置取决于数组的内容。快速排序的大致过程如图 2.3.1 所示。
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
![](https://static001.geekbang.org/resource/image/d0/e4/d0880927e2a522a038be2d04bf19dfe4.png)
快速排序算法是一种高效的排序方法,本文深入介绍了其实现细节和性能特点。通过分治思想和切分过程,快速排序实现了高效的排序。文章详细讲解了切分方法和关键细节,并通过示意图和代码演示了算法的执行流程。此外,还提到了快速排序的三个高层次改进,包括原地切分、避免越界和保持随机性。对快速排序的性能特点进行了分析,指出了其在比较次数和切分不平衡时的低效问题,并提出了随机打乱数组的方法来预防这种情况。文章还探讨了三向切分的快速排序和归并排序的时间复杂度比较,以及对主键概率分布的分析。最后,强调了经过精心调优的快速排序在绝大多数计算机上的绝大多数应用中都会比其他基于比较的排序算法更快,以及快速排序在实际应用中的广泛应用和性能优势。整体内容深入浅出,适合读者快速了解快速排序算法的原理和实现细节,为进一步深入学习和应用提供了基础。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论