如何通过索引对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 占用了很多内存。

这个问题是如何获得排序一个 Vec 的索引？的后续问题。

- Michael Hall

---

改变（或克隆）索引数组i是否是一个问题？如果不是，请查看此解决方案。 - Ömer Erden

从你的例子中并不完全清楚：i 包含输出值应该来自哪个索引，还是输入值应该到哪个索引？也就是说，如果 i = [1, 2, 0]，结果应该是 ["b", "c", "a"] 还是 ["c", "a", "b"]？ - Jmb

我猜OP想要做的是将向量恢复（或“取消排序”）到在调用其他帖子中提到的argsort函数之前的状态。这里的i是argsort的输出，而v是使用argsort排序的。如果是这种情况，我认为["c"，"a"，"b"]将是@Jmb案例的预期结果。 - Joe_Jingyu

感谢澄清，Michael。我误解了索引的含义。现在，kmdreko的解决方案看起来对我来说是正确的。 - Joe_Jingyu

我的解决方案有些 hacky，它的工作原理是因为 Vec::sort 实现通过关注 is_less 来交换元素，但这种行为是封装的，这意味着向后兼容性不能保证，如果你要使用它，请记住这一点。 - Ömer Erden

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）。如果这种方法可以不跟踪排序元素，请随意发表评论或编辑。

- kmdreko

---

这个可以运行。你说的“需要刮擦空间”是什么意思？ 此外，似乎usize::max_value()已被弃用，推荐使用常量usize::MAX。 - Michael Hall

谢谢提醒，我已经更新了。所需的“临时空间”是跟踪每个元素是否已经在其最终排序位置上。它需要这样做，因为在组织早期元素时可能会将后来的元素放在正确的位置上。但无论如何，它都需要遍历整个数组。如果不这样做，它将撤销先前的工作。 - kmdreko

另一种避免使用“魔术”SORTED值的方法是使用indices [idx] == idx作为标记，表示已经在正确位置的元素。 - Jmb

@Jmb 这在索引跳跃时是有效的，但是如何使顶层循环忽略这些元素呢？ - kmdreko

@Jmb能提供一些代码吗？为了让它工作，我必须交换indices和data的元素，对吧？嗯，我想那样可能会好一点。 - kmdreko

Answer 2

以同样的方式，只需自己实现即可。

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

v = i.into_iter().map(|x| v[x]).collect::<Vec<&str>>();

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

- Zeppi

---

不过那还没有安排好。 - Jmb

我并不是在宣称这是正确的想法。我只是在说据我所知没有“sort_by_index”函数的等效函数存在，你必须自己来实现它。我提出了一个想法，就是它所表示的内容。 - Zeppi

Answer 3

您可以创建一个HashMap或BTreeMap 查找表 并将其用作键搜索器：

use std::collections::HashMap;
fn main() {
    let i = vec![0, 3, 2, 1];
    let mut v = vec!["a", "b", "c", "d"];

    let keys: HashMap<_, _> = v.iter().cloned().zip(i.iter()).collect();
    v.sort_by_cached_key(|e| keys[e]);

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

Playground

- Netwave