刷题
刷题
learn
learn
日期
Aug 30, 2024
- 思路：
- 先随机选一个数
x；
- 然后把≤
x的都放在左边，>x的都放在右边；
- 然后把
x和左边的最后一个数换位置；这个操作完了之后，x的位置就固定了，这也是为什么快排更快的原因；
- 最后分别在
x的左侧和右侧递归调用快排；
- 改进版：（如果有多个相同的值，可以一次排好）
- 分为三个区域：<
x、>x和 ==x，用a和b两个下标记录<x和 >x的边界；
i从a开始向b前进，如果遇到>x的就和b交换，同时i不变，b--；如果遇到<x的就和a交换，同时i++，a++；
i越界（到b右边）结束，然后接着在左右递归
- 选择数
x的过程是随机过程，要用期望来分析时间复杂度；
- 如果算法是固定流程，要用最坏情况来估计
- 选择的数字是当前范围上的固定位置，比如范围上最右侧的数字，那么就是普通快速排序； 时间复杂度（因为是固定流程，所以考虑最坏情况：已经是有序），额外空间复杂度；
- 选择的数字是当前范围上的随机位置，那么就是随机快速排序； 随机快速排序，时间复杂度，额外空间复杂度
- 证明：《算法导论-7.4.2》