假设您需要保留一个更改列表,其中可能包含重复值的项目(已排序)。例如,你有[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
您正在寻找的术语是“稳定”排序。一些算法是,有些则不是。 – Crowcoder
啊,谢谢你的提示。现在,我正在阅读关于这个主题的文章。 –