如何按索引对 Vec 进行排序（重新排序）？

Question

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

例如：

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占用大量内存。

这个问题是如何获取对 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;
            }
        }
    }
}

看看它在操场上的工作（@Jmb 的改进）。

否则，您将需要单独分配暂存空间（可能是BitVec）。如果此方法可以在不跟踪排序元素的情况下进行，请随意评论或编辑。