实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| fn q_srot(arr: &Vec<i32>) -> Vec<i32> {
if arr.len() < 2 {
return arr.clone();
}
let base = arr[0];
let small: Vec<i32> = arr.into_iter().filter(|x| *x < &base).map(|x| *x).collect();
let bigger: Vec<i32> = arr.iter().filter(|x| *x > &base).map(|x| *x).collect();
let result: Vec<i32> = q_srot(&small)
.into_iter()
.chain(vec![base])
.chain(q_srot(&bigger))
.collect();
return result;
}
|
理解思路
分治，就是把问题不断的分解，这个问题的最小解就是问题的答案。不是所有的问题都可以使用分治
递归是实现分治的方案
递归实现的两个重要条件
- 基准条件，满足此条件相当于找到最小解，可以结束递归
- 递归条件，如何递归能得到结果
草，写这个东西是真的很困难。
还是需要在理解一下分治