230407-分治-快排

实现

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;
}

理解思路

分治，就是把问题不断的分解，这个问题的最小解就是问题的答案。不是所有的问题都可以使用分治

递归是实现分治的方案

递归实现的两个重要条件

• 基准条件，满足此条件相当于找到最小解，可以结束递归
• 递归条件，如何递归能得到结果

草，写这个东西是真的很困难。

还是需要在理解一下分治