當繼續對列表進行排序時，請保持相同值的項目的相對順序

Question

假設您需要保留一個更改列表，其中可能包含重複值的項目（已排序）。例如，你有[99,99,90,89]，但是第四項的值已經改爲91.你會希望它是[99,99,91,90]，但是你不想要第一個而第二項要改變。

我使用了Sort()方法，但它似乎可能會改變上例中第一項和第二項的順序。有沒有辦法阻止它並保持具有相同值的項目的相對順序？

如果你不能想到這是必要的，那麼假設一個進度表。列表中的項目每秒更新一次。當物品按進度排序時，您希望具有相同進度的物品不斷更改其相對位置。

我已經創建了一個示例代碼來測試它。目標將達到Debug.WriteLine("No change");。

public void Start() 
{ 
    var list = new List<Item>(); 
    var ran = new Random(); 
    const int nItems = 30; 
    for (int i = 0; i < nItems; i++) 
    { 
     var name = "Item " + (list.Count + 1); 
     var item = new Item(name, ran.Next(0, 10)); 
     list.Add(item); 
    } 

    var sorter = new ItemComparer(); 
    var snapshot = new Item[nItems]; 
    for (int nSort = 0; nSort < 10000; nSort++) 
    { 
     list.CopyTo(snapshot); 
     list.Sort(sorter); 

     if (nSort == 0) 
     { 
      //Sorted for the first time, so the snapshot is invalid. 
      continue; 
     } 

     for (int pos = 0; pos < nItems; pos++) 
     { 
      if (snapshot[pos] != list[pos]) 
      { 
       Debug.WriteLine($"Order changed at position {pos} after {nSort} sorts."); 
       PrintChangedLocation(list, snapshot, pos); 
       return; 
      } 
     } 
    } 

    Debug.WriteLine("No change"); 
} 

private static void PrintChangedLocation(List<Item> list, Item[] snapshot, int changedLocation) 
{ 
    Debug.WriteLine($"Before\t\t\tAfter"); 
    for (int pos = 0; pos < list.Count; pos++) 
    { 
     var before = snapshot[pos]; 
     var after = list[pos]; 
     Debug.Write($"{before.Name} = {before.Progress}"); 
     Debug.Write($"\t\t{after.Name} = {after.Progress}"); 

     if (pos == changedLocation) 
     { 
      Debug.Write(" <----"); 
     } 
     Debug.WriteLine(""); 
    } 
} 

class Item 
{ 
    public string Name; 
    public float Progress; 

    public Item(string name, float progress) 
    { 
     Name = name; 
     Progress = progress; 
    } 
} 

class ItemComparer : IComparer<Item> 
{ 
    int Direction = -1; 

    public int Compare(Item x, Item y) 
    { 
     return Direction * (int)(x.Progress - y.Progress); 
    }  
} 

輸出示例：

Order changed at position 12 after 1 sorts. 
Before   After 
Item 7 = 9  Item 7 = 9 
Item 24 = 9  Item 24 = 9 
Item 30 = 8  Item 30 = 8 
Item 4 = 8  Item 4 = 8 
Item 19 = 8  Item 19 = 8 
Item 27 = 7  Item 27 = 7 
Item 5 = 7  Item 5 = 7 
Item 25 = 7  Item 25 = 7 
Item 20 = 7  Item 20 = 7 
Item 26 = 6  Item 26 = 6 
Item 14 = 6  Item 14 = 6 
Item 1 = 6  Item 1 = 6 
Item 28 = 5  Item 2 = 5 <---- 
Item 2 = 5  Item 12 = 5 
Item 12 = 5  Item 28 = 5 
Item 11 = 4  Item 11 = 4 
Item 6 = 4  Item 6 = 4 
Item 13 = 3  Item 13 = 3 
Item 3 = 3  Item 3 = 3 
Item 21 = 3  Item 21 = 3 
Item 10 = 3  Item 10 = 3 
Item 18 = 3  Item 18 = 3 
Item 22 = 2  Item 22 = 2 
Item 29 = 2  Item 29 = 2 
Item 23 = 1  Item 23 = 1 
Item 8 = 1  Item 8 = 1 
Item 17 = 1  Item 17 = 1 
Item 16 = 0  Item 9 = 0 
Item 9 = 0  Item 16 = 0 
Item 15 = 0  Item 15 = 0 

Answer 1

一個值得考慮的選擇將改變：

list.Sort(sorter); 

到：

list = list 
    .Select((item, index) => new { item, index}) 
    .OrderBy(z => z.item, sorter) 
    .ThenBy(z => z.index) 
    .Select(z => z.item) 
    .ToList(); 

這允許你按你的比較器，然後由其在List中的位置 - 從而保持相對順序。