Rust实现泛型快速排序时切片取值报未实现Copy trait错误

问题复现 #

使用i32具体类型实现快速排序可正常运行，替换为泛型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`

错误原因 #

1. 第一个错误源于所有权规则：直接通过索引取值slice[end]会尝试将切片中的元素移动到pivot变量，但切片只是对内存序列的可变借用，不拥有元素所有权，且泛型T没有绑定Copy特征，无法自动复制元素，因此移动操作被禁止。
2. 第二个错误源于类型不匹配：修改后pivot是&T类型的引用，而比较符左侧slice[j]是T类型，Rust不会自动跨类型做解引用比较，因此类型校验失败。
3. 初始代码还存在逻辑错误：分区循环中错误比较了slice[j]与pivot，正确逻辑应该比较当前遍历位置i对应的元素，否则分区逻辑失效，排序结果不符合预期。

修复方案 #

• 方案1（兼容性最优，推荐）
  不要求T实现Copy特征，通过引用完成比较，支持所有实现Ord特征的类型（包括String等非复制类型）。仅需修正partition函数即可：

fn partition<T: Ord>(slice: &mut [T]) -> usize {
    let end = slice.len() - 1;
    // 仅获取pivot的引用，不移动元素
    let pivot = &slice[end];
    let mut j = 0;
    for i in 0..end {
        // 比较时统一使用引用匹配类型，同时修正比较位置为i
        if &slice[i] <= pivot {
            slice.swap(i, j);
            j += 1;
        }
    }
    slice.swap(end, j);
    j
}

quick_sort函数无需修改，修复后可正常编译运行，支持所有可排序类型。

• 方案2（简单但场景受限）
  如果仅需要对可复制的基础类型排序，可以给泛型添加Copy约束，此时直接复制pivot元素即可，无需处理引用：

// 给T添加Copy约束
fn partition<T: Ord + Copy>(slice: &mut [T]) -> usize {
    let end = slice.len() - 1;
    let pivot = slice[end]; // 此时为复制操作，不会触发移动错误
    let mut j = 0;
    for i in 0..end {
        // 修正比较位置为i
        if slice[i] <= pivot {
            slice.swap(i, j);
            j += 1;
        }
    }
    slice.swap(end, j);
    j
}

// 同步给quick_sort添加Copy约束
fn quick_sort<T: Ord + Copy>(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]);
    }
}

该方案写法更直观，但无法对String、Vec等非Copy类型排序，适用场景有限。

内容的提问来源于stack exchange，提问作者user15183525