今天刷题刷到一道题目关于快速排序的。
1. 快速排序的正常发挥（理想情况）
快速排序的核心思想是“找基准，分两边”： 随便挑一个数字（通常挑第一个）当“基准（Pivot）”，然后把比它小的都扔到它左边，比它大的都扔到它右边。
- 理想状态：每次你挑的这个基准数，刚好大小排在正中间。这样每次都能把数据完美劈成两半。就像切西瓜，对半切、再对半切，效率极高。
2. 什么叫“最坏的情况”？
最坏的情况发生在数组已经是有序的（不管是正序还是逆序），而你每次都死板地选第一个数当基准。
举个极端的例子：你要对 [1, 2, 3, 4, 5] 进行快速排序。
- 第 1 趟：你选
1当基准。拿它跟后面的数字比了一圈（比较了 4 次），发现大家都比它大。结果左边空空如也，右边剩下[2, 3, 4, 5]。这根本没起到“劈成两半”的作用，只是切下了一个小边边！ - 第 2 趟：对剩下的
[2, 3, 4, 5]，你选2当基准。又比了一圈（比较了 3 次），结果还是全在右边。 - 第 3 趟：比较了 2 次。
- 第 4 趟：比较了 1 次。
3. 为什么是 O(n²)？
你会发现，这原本极其聪明的快速排序，在最坏的情况下，竟然堕落成了我们之前讲过的冒泡排序！ 每次只能确定一个元素的位置，总共需要的比较次数变成了等差数列求和：
(n−1)+(n−2)+⋯+1=n(n−1)/2
在计算时间复杂度（大 O 记法）时，我们只看最高次幂，忽略常数项和低次幂，最终简化表达为 O(n²)。