随机排列等元素的比较法

正如夏普图思所说,您可以存储每次比较的结果,然后再次查看它们。

但这并不有趣,而且它增加了时间复杂性和空间复杂性,因为您必须存储以前的比较,并在每次进行比较时搜索它们。

所以我要做的是: 在搜索开始时,随机获得一个种子。 然后编写一个基于t和种子创建哈希的函数。

public int Hash(T a, int s)
{
    // e.g.
    return Random( a.Name().ToInt() + s ).NextDouble();
}

public int Compare(T x, T y, int s)
{
    if (x.Equals(y)) return 0;

    int result = _comparer(x, y);

    if (result != 0) return result;

    return (Hash(x, s) < Hash(y, s) ) ? -1 : 1;
}

这在给定的排序中是稳定的,但不需要查找表。

先随机洗牌,然后使用 稳定的 排序。

问题是比较的结果在排序时是不可复制的。排序算法可以对给定的一对元素多次调用比较方法,比较方法每次应返回相同的值。

您可以存储涉及随机随机随机洗牌的每个比较的结果,并在为相应的对再次调用比较方法时查找它们。

如果您只控制排序方法,那么您将受到严重限制,因为您不知道将在哪个排序算法中使用它。你必须保留相同关键值之间任何比较的随机结果,并在表格中查找相同值之间的任何新比较,以确保在任何单个排序运行中都能得到相同、稳定的结果,如夏普图斯所说。

不是一个严格的比较方法,但是如果您随机化了一个快速排序算法,将键等于轴值的任何值细分到哪个分区中,该怎么办?递归细分会随机地在左侧放置一些相等的值,而在右侧放置一些相等的值。