递归 - 实现快速排序求解（已结）

作者 xinlingjushi 2021-03-05 10:43

感谢，我的意思是我先完成自己的逻辑，然后再进一步考虑性能什么的。毕竟刚接触还是循序渐进，毕竟我的思路不仅仅是性能或者效率方面的问题，我更想通过它了解的是Rust语言的特性，以及对应要改变的编程思维，您提供的我会吸收了解的。就比如说我需要1块钱，你给我一块金子，真的一时消化不了，只能慢慢来，再次感谢回帖的大佬们。

👇
Bai-Jinlin: 最后一次回你了，你真正想要的效果需要这么写，但是这么写根本不如原地切分好。

fn qsort<T: PartialOrd + Clone>(a: &[T]) -> Vec<T> {
    use rand::seq::SliceRandom;
    use rand::thread_rng;
    let mut a = a.to_vec();
    a.shuffle(&mut thread_rng());
    _qsort(a)
}
fn _qsort<T: PartialOrd + Clone>(a: Vec<T>) -> Vec<T> {
    if a.len() <= 1 {
        return a;
    }
    let (x, xs) = a.split_at(1);
    let mut l = xs.iter().filter(|v| *v<=&x[0]).cloned().collect::<Vec<T>>();
    let mut r = xs.iter().filter(|v| *v>&x[0]).cloned().collect::<Vec<T>>();

    l = _qsort(l);
    r = _qsort(r);
    l.push(x[0].clone());
    l.append(&mut r);
    l
}

fn main() {
    let a = [3, 5, 8, 1, 2, 9, 4, 7, 6];
    assert_eq!(qsort(&a), [1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

--
👇
xinlingjushi: use rand::Rng; fn main() { let mut list = vec![3, 5, 8, 1, 2, 9, 4, 7, 6]; quick_sort(&mut list); assert_eq!(list, [1, 2, 3, 4, 5, 6, 7, 8, 9]); } fn quick_sort<T: PartialOrd + Copy>(list: &mut Vec) -> &mut Vec { if list.len() > 1 { //获取随机基准值 let elme = list[rand::thread_rng().gen_range(1, list.len())]; let (mut left, mut right) = (Vec::new(), Vec::new()); //根据基准值比较,排序后的值放在左边还是右边 for num in list.iter_mut() { if *num == elme { continue; } else if *num < elme { left.push(*num); } else { right.push(*num); } } //递归调用分治 let (mut left, mut right) = (quick_sort(&mut left), quick_sort(&mut right)); left.push(elme); left.append(&mut right); //由于无法返回不同的声明周期的Vec，转而求其次，重新赋值 list.truncate(0); //清理 list.append(&mut left); //装弹 } list }

谢谢回帖的大佬们，自己结帖吧。还是按自己的逻辑做吧，感觉实现后对声明周期有了更深入的了解。

Bai-Jinlin 2021-03-04 23:56

最后一次回你了，你真正想要的效果需要这么写，但是这么写根本不如原地切分好。

fn qsort<T: PartialOrd + Clone>(a: &[T]) -> Vec<T> {
    use rand::seq::SliceRandom;
    use rand::thread_rng;
    let mut a = a.to_vec();
    a.shuffle(&mut thread_rng());
    _qsort(a)
}
fn _qsort<T: PartialOrd + Clone>(a: Vec<T>) -> Vec<T> {
    if a.len() <= 1 {
        return a;
    }
    let (x, xs) = a.split_at(1);
    let mut l = xs.iter().filter(|v| *v<=&x[0]).cloned().collect::<Vec<T>>();
    let mut r = xs.iter().filter(|v| *v>&x[0]).cloned().collect::<Vec<T>>();

    l = _qsort(l);
    r = _qsort(r);
    l.push(x[0].clone());
    l.append(&mut r);
    l
}

fn main() {
    let a = [3, 5, 8, 1, 2, 9, 4, 7, 6];
    assert_eq!(qsort(&a), [1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

--
👇
xinlingjushi: use rand::Rng; fn main() { let mut list = vec![3, 5, 8, 1, 2, 9, 4, 7, 6]; quick_sort(&mut list); assert_eq!(list, [1, 2, 3, 4, 5, 6, 7, 8, 9]); } fn quick_sort<T: PartialOrd + Copy>(list: &mut Vec) -> &mut Vec { if list.len() > 1 { //获取随机基准值 let elme = list[rand::thread_rng().gen_range(1, list.len())]; let (mut left, mut right) = (Vec::new(), Vec::new()); //根据基准值比较,排序后的值放在左边还是右边 for num in list.iter_mut() { if *num == elme { continue; } else if *num < elme { left.push(*num); } else { right.push(*num); } } //递归调用分治 let (mut left, mut right) = (quick_sort(&mut left), quick_sort(&mut right)); left.push(elme); left.append(&mut right); //由于无法返回不同的声明周期的Vec，转而求其次，重新赋值 list.truncate(0); //清理 list.append(&mut left); //装弹 } list }

谢谢回帖的大佬们，自己结帖吧。还是按自己的逻辑做吧，感觉实现后对声明周期有了更深入的了解。

作者 xinlingjushi 2021-03-04 22:21

use rand::Rng; fn main() { let mut list = vec![3, 5, 8, 1, 2, 9, 4, 7, 6]; quick_sort(&mut list); assert_eq!(list, [1, 2, 3, 4, 5, 6, 7, 8, 9]); } fn quick_sort<T: PartialOrd + Copy>(list: &mut Vec) -> &mut Vec { if list.len() > 1 { //获取随机基准值 let elme = list[rand::thread_rng().gen_range(1, list.len())]; let (mut left, mut right) = (Vec::new(), Vec::new()); //根据基准值比较,排序后的值放在左边还是右边 for num in list.iter_mut() { if *num == elme { continue; } else if *num < elme { left.push(*num); } else { right.push(*num); } } //递归调用分治 let (mut left, mut right) = (quick_sort(&mut left), quick_sort(&mut right)); left.push(elme); left.append(&mut right); //由于无法返回不同的声明周期的Vec，转而求其次，重新赋值 list.truncate(0); //清理 list.append(&mut left); //装弹 } list }

谢谢回帖的大佬们，自己结帖吧。还是按自己的逻辑做吧，感觉实现后对声明周期有了更深入的了解。

Bai-Jinlin 2021-03-04 19:16

快速排序的主要思想是分治，在这个演示代码里随机基准值那些东西根本就不重要，反正实践的话的话要么就排序之前先把数组全部随机打乱一下，就算真要随机基准值的话也就加两行代码就解决了，相反你的快速排序为了划分出比基准值大和小的元素还用了两个辅助的堆上数组，而不是原地划分然后传切片递归，用辅助数组不仅push里可能的扩展内存触发的copy需要时间，append更需要大量时间，你应该参照一下下面AbdyCjen写的代码，他写和演示里的思路一样，并且更加的Rust化。

--
👇
xinlingjushi: 本身就是错的，我标//?问号的地方，这个是我用java实现后，翻译过来的，会有差异

--
👇
Bai-Jinlin: 笑死我了伙计，你把这个代码看懂再说吧。你要是想代码有返回值也只需要把这个代码稍微改一下就行。

--
👇
xinlingjushi: 快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。 [ 比基准值小的数 ] 基准值 [ 比基准值大的数 ] 接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序

你这个好像并不是快速排序，而且我需要递归是有返回值的，显然它不符合我的要求

--
👇
Bai-Jinlin: https://github.com/TheAlgorithms/Rust/blob/master/src/sorting/quick_sort.rs

作者 xinlingjushi 2021-03-04 09:22

谢谢，刚接触rust，很多东西还不清楚，慢慢积累吧

--
👇
johnmave126: 这个快速排序的签名设计就挺有问题的，不考虑这个签名，最大程度上保持你原来代码原意的话大概是这样:playground

要好好写的话，先考虑你是要原地排序还是非原地排序。然后分组可以用std::iter::Iterator::partition来做。

作者 xinlingjushi 2021-03-04 09:19

本身就是错的，我标//?问号的地方，这个是我用java实现后，翻译过来的，会有差异

--
👇
Bai-Jinlin: 笑死我了伙计，你把这个代码看懂再说吧。你要是想代码有返回值也只需要把这个代码稍微改一下就行。

--
👇
xinlingjushi: 快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。 [ 比基准值小的数 ] 基准值 [ 比基准值大的数 ] 接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序

你这个好像并不是快速排序，而且我需要递归是有返回值的，显然它不符合我的要求

--
👇
Bai-Jinlin: https://github.com/TheAlgorithms/Rust/blob/master/src/sorting/quick_sort.rs

作者 xinlingjushi 2021-03-04 09:18

序列中随机选择一个基准值，这个并没有体现啊

👇
Bai-Jinlin: 笑死我了伙计，你把这个代码看懂再说吧。你要是想代码有返回值也只需要把这个代码稍微改一下就行。

--
👇
xinlingjushi: 快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。 [ 比基准值小的数 ] 基准值 [ 比基准值大的数 ] 接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序

你这个好像并不是快速排序，而且我需要递归是有返回值的，显然它不符合我的要求

--
👇
Bai-Jinlin: https://github.com/TheAlgorithms/Rust/blob/master/src/sorting/quick_sort.rs

AbdyCjen 2021-03-03 13:01

pub fn quick_sort<T>(iv: &mut [T])
where T: std::cmp::Ord {
	if iv.len() <= 1 {
		return;
	}
	let (mut i, mut j, mut k) = (0, 0, iv.len() - 1);
	{
		let (o, iv) = iv.split_at_mut(1);
		while j < k {
			match iv[j].cmp(&o[0]) {
				Ordering::Less => {
					iv.swap(j, i);
					i += 1;
					j += 1;
				}
				Ordering::Greater => {
					iv.swap(j, k - 1);
					k -= 1;
				}
				Ordering::Equal => j += 1,
			}
		}
	}
	iv.swap(0, i);
	quick_sort(&mut iv[..i]);
	quick_sort(&mut iv[k + 1..]);
}

你这函数签名就离谱,实现也丑,还编译不过;

Bai-Jinlin 2021-03-03 12:38

笑死我了伙计，你把这个代码看懂再说吧。你要是想代码有返回值也只需要把这个代码稍微改一下就行。

--
👇
xinlingjushi: 快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。 [ 比基准值小的数 ] 基准值 [ 比基准值大的数 ] 接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序

你这个好像并不是快速排序，而且我需要递归是有返回值的，显然它不符合我的要求

--
👇
Bai-Jinlin: https://github.com/TheAlgorithms/Rust/blob/master/src/sorting/quick_sort.rs

johnmave126 2021-03-03 12:26

这个快速排序的签名设计就挺有问题的，不考虑这个签名，最大程度上保持你原来代码原意的话大概是这样:playground

要好好写的话，先考虑你是要原地排序还是非原地排序。然后分组可以用std::iter::Iterator::partition来做。

作者 xinlingjushi 2021-03-03 09:53

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。 [ 比基准值小的数 ] 基准值 [ 比基准值大的数 ] 接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序

你这个好像并不是快速排序，而且我需要递归是有返回值的，显然它不符合我的要求

--
👇
Bai-Jinlin: https://github.com/TheAlgorithms/Rust/blob/master/src/sorting/quick_sort.rs

Bai-Jinlin 2021-03-02 22:20

https://github.com/TheAlgorithms/Rust/blob/master/src/sorting/quick_sort.rs

作者 xinlingjushi 2021-03-02 16:27

已改

--
👇
Mike Tang: markdown格式包一下

Mike Tang 2021-03-02 14:25

markdown格式包一下

递归 - 实现快速排序求解（已结）

评论区

序列中随机选择一个基准值，这个并没有体现啊