sorting - 如何按索引对 Vec 进行排序？

Question

我想按 Rust 中的预定义顺序就地对 Vec 进行排序(重新排序)。

例如:

let i = vec![0, 3, 2, 1];
let mut v = vec!["a", "b", "c", "d"];
v.sort_by_indices(&i);

assert_eq!(v, &["a", "d", "c", "b"]);

我想就地执行此操作。在我的用例中，v 占用大量内存。

此问题是 How to get the indices that would sort a Vec? 的后续问题

Answer 1

就地实现很棘手，但可以在 O(n) 时间内实现。它通过追踪索引和交换元素来工作，直到它回到它开始的地方。不幸的是，这确实需要暂存空间来跟踪哪些元素已经排序。这是一个在允许使用索引数组的情况下重用索引数组的实现:

fn sort_by_indices<T>(data: &mut [T], mut indices: Vec<usize>) {
    for idx in 0..data.len() {
        if indices[idx] != idx {
            let mut current_idx = idx;
            loop {
                let target_idx = indices[current_idx];
                indices[current_idx] = current_idx;
                if indices[target_idx] == target_idx {
                    break;
                }
                data.swap(current_idx, target_idx);
                current_idx = target_idx;
            }
        }
    }
}

查看它在 playground 上的工作(@Jmb 进行了改进)。

否则您需要为暂存空间单独分配(可能是 BitVec )。如果此方法可行而无需跟踪已排序的元素，请随意评论或编辑。