首先，我知道Fisher-Yates shuffle。但是，为了争论，我想允许用户从下拉列表中选择一个排序选项。该列表将包括一个“随机”选项。根据他们的选择结果，我只想用 IComparer 实例替换我的排序。IComparer 会是什么样子？
谷歌提出了大量有缺陷的结果，它们都采用这种形式：
public class NaiveRandomizer<T> : IComparer<T>
{
private static Random rand = new Random();
public int Compare(T x, T y)
{
return (x.Equals(y))?0:rand.Next(-1, 2);
}
}
但是，这种实现是有偏见的，在某些情况下甚至会抛出异常。偏差可以用下面的代码来证明：
void Test()
{
Console.WriteLine("NaiveRandomizer Test:");
var data = new List<int>() {1,2,3};
var sortCounts = new Dictionary<string, int>(6);
var randomly = new NaiveRandomizer<int>();
for (int i=0;i<10000;i++)
{ //always start with same list, in _the same order_.
var dataCopy = new List<int>(data);
dataCopy.Sort(randomly);
var key = WriteList(dataCopy);
if (sortCounts.ContainsKey(key))
sortCounts[key]++;
else
sortCounts.Add(key, 1);
}
foreach (KeyValuePair<string, int> item in sortCounts)
Console.WriteLine(item.Key + "\t" + item.Value);
}
string WriteList<T>(List<T> list)
{
string delim = "";
string result = "";
foreach(T item in list)
{
result += delim + item.ToString();
delim = ", ";
}
return result;
}
那么如何实现一个随机IComparer<T>的来解决这些问题呢？允许要求每次调用都.Sort()使用单独的 IComparer 实例，因为我看不到任何其他方法可以做到这一点：必须使用其他一些真正随机的值来比较项目，但该值也必须与项目一致在给定的排序操作中。
我在这里有一个开始，但它是匆忙发布的，非常慢，甚至没有返回所有可能的类型（测试表明它至少消除了偏见，如果你不计算缺失的选项）。我不希望像 Fisher-Yates 那样的 O(n) 性能，但我确实想要一些合理的东西（n log n 表示小的 n），我确实希望它能够显示所有可能的类型。不幸的是，该链接是该问题的当前公认答案，因此我希望能够用更好的东西替换它。
如果不出意外，我希望这能吸引所有那些寻找 IComparable 解决方案的谷歌查询——他们最终会在这里而不是在其他地方告诉他们使用不正确的版本。