1. 快速排序
1. 1 思想
- 确定分界点
- q[l] (用j)
- q[r] (用i)
- q[(l+r)/2]
- q[random]
- 调整区间(*)
- 左边<=x x0 右边>=x
- x不一定在x0位置
- 递归两端
1 | 1. 暴力求解 |
1.2 算法模板
1 |
|
1 | //输入 |
c++里的快排是快排与插排的组合。
快排一般做题不会遇到,在面试的时候要你手写。
当分界点选择为a[l]时,如果使用i分割左右,那么可能会死循环,例如[0,1]用i分割后左:[],右:[0,1]死循环。所以
mid = a[l]
时,递归用(a, l, j)
。反之同理。可以考虑使用i或j
可以考虑使用while(a[i++])
快排不稳定,如果要变成稳定的,可以变成<a[i], i>
循环最终只会有两种情况:
- i==j
- i==j+1
1.3 练习
1.3.1 第k个数
给定一个长度为 n的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n个整数(所有整数均在1~109范围内),表示整数数列。
输出格式
- 输出一个整数,表示数列的第 k小数。
数据范围
1≤n≤100000
1≤k≤n
输入样例:
1
25 3
2 4 1 5 3输出样例:
1
3
解1
- 先快排,然后输出第k个数
1 |
|
解2
快速选择:O(n)
- 确定分界点
- q[l]
- q[r]
- q[(l+r)/2]
- q[random]
- 调整区间(*)
- 左边<=x x0 右边>=x
- x不一定在x0位置
- if 左区间长度sl >= k, 递归左区间
- else 左区间长度sl < k, 递归右区间(更新k)
- 确定分界点
1 |
|