如何對列表進行排序，將地圖從舊位置保存到新位置？

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 

然後，因爲「一次」從位置0移動到位置3，在地圖將是

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

所以，對於所有的i

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

你必須使用之後的新索引210：

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 } 

更新：ACC。評論：「我如何獲得'新索引'的舊索引'數據結構？」

你可以使用字典：

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