快速排序(quick sort)的特点是分块排序,也叫划分交换排序(partition-exchange sort)
代码实现方式可以有这么几种:
- 拼接结果
- 左右相互交换
- 快慢指针
1. 拼接结果
# Python3 |
这种方式最直观,最好理解,但效率不高。为了找出大于和小于中位数的元素,循环遍历了 2 次
做一点小小的修改,改为一次遍历:
class Solution: |
优化后,运行时间降低了,但空间使用还很高,每次递归都额外需要 2 个平均长度为 ¼ n 的数组
1 + 2 ... + n-1 + n = ((n + 1) * n ) / 2 |
2. 左右相互交换
其实可以不使用额外空间,直接操作原数组。选择一个基准值,将小于它和大于它的元素相互交换。
class Solution: |
使用此种方式,最好要将开头(或末尾)的元素设为基准值。如果使用中间元素,也最好先交换到开头(或末尾),否则将考虑大量场景。
排序过程:
[6 5 3 1 8 7 2 4] |
nums[left] <= pivot 时:
[6 7 3 4 8 1 2 5] |
3. 快慢指针
上面这种方式其实使用两个相向指针,也可以使用同向快慢指针实现元素交换。
class Solution: |
排序过程:
[6 5 3 1 8 7 2 4] |
随机选择可以增加每次选择的基准值为中位数的几率
时间复杂度
最坏时间复杂度
每次基准值都是最大 (或最小)值时,所需递归次数最多,有两种情况:
- 数组有序时,每次使用最后 1 位(或第 1 位)作为基准值
1 2 3 4 5 6 7 8 |
- 随机选择时,每次选择到最大(或最小)的一位
6 7 3 4 8 1 2 5 |
此时递归次数为 n + 1,平均每次排序 ½ n 个数。所以最坏时间复杂度:O(n^2)。
最好时间复杂度
如果每次选择中位数作为基准值,递归次数会减少么?其实不会减少,但递归中遍历的次数会减少。如果每层遍历看成 n 次的话,可以用下面的这个图表示:
所以最好时间复杂度为:O(n * log n)
平均时间复杂度
最坏时间复杂度的情况很少见,所以平均时间复杂度就是最好时间复杂度 O(n * log n)
空间复杂度
每次递归均会使用额外空间,所以空间复杂度跟递归次数有关。
最坏时间复杂度时,最坏空间复杂度也为 O(n)。最好时间复杂度时时,虽然递归没有减少,但当只有 1 个或 0 个元素时,没有使用额外空间,直接返回,所以最好空间复杂度为 O(log n)。平均时间复杂度也为 O(log n)。
第 1 种实现因为使用额外数组,最坏空间复杂度为 O(n^2),最好空间复杂度为 O(n * log n),
测试代码
import logging |
测试用例
[3, 2, 1, 5, 6, 4] |