我试图在Rust中编写快速排序,当我使用特定类型[i32]时,它可以正常工作,但当我try 使用[T]时,出现了一个错误.

fn main() {
    let mut arr = vec![4,3,2,1];
    quick_sort(&mut arr);
    println!("{:?}", arr);
}

fn partition<T: Ord>(slice: &mut [T]) -> usize {
    let end = slice.len() - 1;
    let pivot = slice[end];
    let mut j = 0;
    for i in 0..end {
        if slice[j] <= pivot {
            slice.swap(i, j);
            j += 1;
        }
    }
    slice.swap(end, j);
    j
}

fn quick_sort<T: Ord>(slice: &mut [T]) {
    if !slice.is_empty() {
        let j = partition(slice);
        let len = slice.len();
        
        quick_sort(&mut slice[0..j]);
        quick_sort(&mut slice[j+1..len]);
    }
}

我得到以下错误:

error[E0508]: cannot move out of type `[T]`, a non-copy slice
  --> src/main.rs:9:17
   |
  9|     let pivot = slice[end];
   |                 ^^^^^^^^^^ cannot move out of here
   |                            move occurs because `slice[_]` has type `T`, 
   |                            which does not implement the `Copy` trait
   |                            help: consider borrowing here: `&slice[end]`

当为let pivot = &slice[end];时,我得到一个不同的错误:

error[E0308]: mismatched types
  --> src/main.rs:12:22
   |
  7| fn partition<T: Ord>(slice: &mut [T]) -> usize {
   |              - this type parameter
...
 12|        if slice[j] <= pivot {
   |                       ^^^^^ expected type parameter `T`, found `&T`
   = note: expected type parameter `T`
                   found reference `&T`

我不能让它与[T]一起工作.

推荐答案

我们可以通过将if更改为:

if &slice[j] <= pivot {

但这又遇到了另一个错误:

error[E0502]: cannot borrow `*slice` as mutable because it is also borrowed as immutable
  --> src/main.rs:13:13
   |
9  |     let pivot = &slice[end];
   |                 ----------- immutable borrow occurs here
...
12 |         if &slice[j] <= pivot {
   |                         ----- immutable borrow later used here
13 |             slice.swap(i, j);
   |             ^^^^^^^^^^^^^^^^ mutable borrow occurs here

这是因为我们正在从切片中获取一个值的引用,并且当该引用处于活动状态时,我们正在调用一个需要对切片进行可变访问的方法.

要解决此问题,我们可以将引用内联到if语句本身中:

fn partition<T: Ord>(slice: &mut [T]) -> usize {
    let end = slice.len() - 1;
    let mut j = 0;
    for i in 0..end {
        if slice[j] <= slice[end] {
            slice.swap(i, j);
            j += 1;
        }
    }
    slice.swap(end, j);
    j
}

输出:

[1, 2, 3, 4]

Playground


这对[i32]有效的原因是调用slice[end]隐式创建了值的副本,因为i32实现了Copy特性.如果类型未实现Copy,则需要使用&slice[index]获取引用,或者如果它实现Clone,则调用slice[index].clone().在这段代码中,您有一个通用的T,它不实现这两个.

Rust相关问答推荐

为什么在Rust struct 中只允许最后一个字段具有动态大小的类型

MacOS(AARCH64)上Ghidra中的二进制补丁导致进程终止

当两者都有效时,为什么Rust编译器建议添加';&;而不是';*';?

异步FN中的 rust 递归

如何使用盒装枚举进行模式匹配?

当T不执行Copy时,如何返回Arc Mutex T后面的值?

如果死 struct 实现了/派生了一些特征,为什么Rust会停止检测它们?

如何在AVX2中对齐/旋转256位向量?

borrow 是由于对 `std::sync::Mutex>` 的解引用强制而发生的

tokio::sync::broadcast::Receiver 不是克隆

`UnsafeCell` 在没有锁定的情况下跨线程共享 - 这可能会导致 UB,对吗?

如何以与平台无关的方式将OsString转换为utf-8编码的字符串?

为什么 Rust 字符串没有短字符串优化 (SSO)?

push 方法是否取得所有权?

Some(v) 和 Some(&v) 有什么区别?

为什么在 macOS / iOS 上切换 WiFi 网络时 reqwest 响应会挂起?

判断 is_ok 后重用结果

如何在 Rust 中返回通用 struct

Rust 生命周期:不能在方法内重新borrow 可变字段

为什么 u64::trailing_zeros() 在无分支工作时生成分支程序集?