c# - 如何对列表进行排序，将 map 从旧位置保存到新位置？

Question

我想对列表进行排序，并保存从元素的旧位置到新位置的映射？

例如，如果要排序的列表是

var words = "once upon a midnight dreary".Split();
// once upon a midnight dreary

那么排序后的列表就是

var orderedWords = words.OrderBy(w => w).ToArray();
// a dreary midnight once upon

然后因为 'once' 从位置 0 移动到位置 3， map 将是

0 => 3, 1 => 4, 2 => 0, 3 => 2, 4 => 1

所以，对于我来说

words[i] = orderedWords[map[i]]

我该怎么做？我希望它的时间复杂度应该与普通排序相同，即。 O(n log n)

---

我试过:

var map = words.Select((word, index) => new { Word = word, Index = index}).OrderBy(x => x.Word).Select(x => x.Index);

但这给出了

> 2, 4, 3, 0, 1

这不符合我上面给出的身份

for(int i = 0; i < words.Length; i++)
    Assert.AreEqual(words[i], orderedWords[map[i]]);

Answer 1

您必须在 OrderBy 之后使用新索引:

var map = words
    .Select((word, index) => new { Word = word, Index = index })
    .OrderBy(x => x.Word)
    .Select((x, NewIndex) => new { x.Word, x.Index, NewIndex });

结果:

[0] { Word = "a", Index = 2, NewIndex = 0 } 
[1] { Word = "dreary", Index = 4, NewIndex = 1 }    
[2] { Word = "midnight", Index = 3, NewIndex = 2 }
[3] { Word = "once", Index = 0, NewIndex = 3 }  
[4] { Word = "upon", Index = 1, NewIndex = 4 }  

更新:符合。评论:“我如何得到‘旧索引到新索引’数据结构？”

你可以使用字典:

var map = words
    .Select((word, index) => new { Word = word, OldIndex = index })
    .OrderBy(x => x.Word)
    .Select((x, NewIndex) => new { x.Word, x.OldIndex, NewIndex })
    .ToDictionary(x => x.OldIndex, x => x.NewIndex);

for (int i = 0; i < words.Length; i++)
{
     Console.WriteLine("Word: {0} \tOldIndex: {1} \tNewIndex: {2}", words[i], i, map[i]);
}

结果:

Word: once      OldIndex: 0     NewIndex: 3
Word: upon      OldIndex: 1     NewIndex: 4
Word: a         OldIndex: 2     NewIndex: 0
Word: midnight  OldIndex: 3     NewIndex: 2
Word: dreary    OldIndex: 4     NewIndex: 1