为什么在排序中使用Random导致[无法排序IComparer.Compare错误]

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

不仅需要比较关系保持一致,还需要强加总排序.例如,你不能说"袜子比鞋子小,衬衫既不小于也不比裤子小",等等等等,把它作为一种排序算法,并期望从另一端得到拓扑.比较排序称为比较排序,因为它们需要格式良好的比较关系.特别是,如果比较关系不一致,传递和总排序,则快速排序可以永久运行或给出无意义的结果.

如果你想要的是一个shuffle然后实现Fischer-Yates shuffle.(做得正确;即使算法很简单,它几乎总是被实现错误.)如果你想要的是拓扑排序,那么实现拓扑排序.使用正确的工具完成工作.

Answer 2

因为正如错误所说，随机不一致。您必须有一个比较器，当给定相同的参数时，该比较器始终返回相同的结果。否则排序将不一致。

Knuth 有一种随机排序算法，其工作方式类似于插入排序，但您将值与现有数组中随机选择的位置进行了交换。