我想通過 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占用大量記憶體。
注意：這個問題是如何獲得在 Rust 中對向量進行排序的索引的自然后續問題？
uj5u.com熱心網友回復：
就地實作很棘手，但在 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 改進）。
否則，您將需要為暫存空間單獨分配（可能是 a BitVec）。如果可以在不跟蹤已排序元素的情況下使用此方法，請隨時發表評論或編輯。
uj5u.com熱心網友回復：
以同樣的方式實作自己
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"]);
uj5u.com熱心網友回復：
您可以創建一個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"]);
}
操場
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/351252.html