c# - 为什么在 Sort 中使用 Random 会导致 [Unable to sort IComparer.Compare error]

Question

我尝试使用任一代码对字节列表 (List) 进行混洗:

myList.Sort((a, b) => this._Rnd.Next(-1, 1));

或

myList.Sort(delegate(byte b1, byte b2)
{
    return this._Rnd.Next(-1, 1);
});

然后他们抛出以下错误:

无法排序，因为 IComparer.Compare() 方法返回不一致的结果。一个值与自身比较不相等，或者一个值反复与另一个值比较会产生不同的结果。 x:“{0}”，x 的类型:“{1}”，IComparer:“{2}”。

使用随机而不是字节的比较功能有什么问题？

我尝试改用 LINQ 函数并且它有效。

var myNewList = myList.OrderBy(s => Guid.NewGuid());
var myNewList = myList.OrderBy(s => this._Rnd.NextDouble());

我确实读到这些方法比 Fisher-Yates shuffle 慢，仅提供 O(n) 运行时间。但只是想知道如何使用 Sort 函数和随机数。

Answer 1

不仅要求比较关系一致，还要求强加一个全序。例如，您不能说“ socks 比鞋子小，衬衫既不小于也不大于裤子”等等等等，将其输入排序算法并期望从中得到拓扑排序另外一端。比较排序之所以称为比较排序，是因为它们需要格式正确的比较关系。特别是，如果比较关系不一致、传递和全序，快速排序可能永远运行或给出无意义的结果。

如果您想要的是洗牌，则实现 Fischer-Yates 洗牌。 (正确地做；即使算法很简单，它几乎总是被错误地实现。)如果你想要的是拓扑排序，那么就实现拓扑排序。为工作使用正确的工具。