algorithm - sortedArrayUsingComparator 是随机化 NSArray 的安全方法吗？

Question

我之前在搞乱 NSArray 函数，我想我可能碰巧遇到了随机化 NSArray 的最简单方法:

NSArray *randomize(NSArray *arr)
{
    return [arr sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        return arc4random_uniform(3) - 1; // one of -1, 0, or 1
    }];
}

理论上，应该彻底随机化 NSArray。然而，经过深思熟虑，我想知道这是否可能是不安全的，并且理论上会变成一个无限循环，具体取决于 NSArray 使用的排序算法。

我在大小为 10 - 100000 的数组上对此进行了测试，我看到了线性性能差异(每次随机化大约 N * (log10(N) + 2) 比较)，这不是不好。

但是，是否存在 NSArray 理论上永远无法自行排序并导致应用程序崩溃的情况？在我看来，这不应该发生，但你永远不知道。

Answer 1

我认为这取决于底层排序算法。

考虑如果底层排序是冒泡排序会发生什么。这意味着无论何时比较一对元素，都有 1/3 的机会交换它们(如果比较使它们出现乱序)。因此，如果您要使用此比较函数对包含 n 个元素的数组进行排序，则算法在每一步终止的概率等于没有任何比较计算结果为“无序”的概率。由于每次比较都以 1/3 的概率表示“乱序”，这意味着算法在每次迭代中终止的概率为 (2/3)ⁿ。这意味着算法终止前的预期迭代次数为 (3/2)ⁿ = 3ⁿ/2ⁿ。如果您尝试对一个合理大小的数组(例如，n = 1000)运行此算法，那么预期的迭代次数将大得惊人； n = 1000 给出 1.233840597×10¹⁷⁶ 预期迭代!该算法最终会终止，但预期的运行时间太长了，从实际角度来看，它实际上是无限的。

另一方面，如果您尝试使用不同的算法，例如选择排序，则不能保证获得均匀分布。例如，考虑算法的第一遍，它将找到要放在位置 1 的元素。数组中的每个元素(如果分布真的是均匀的)应该有 1/n 的概率被放在第一位。但这种情况并非如此。请注意，第一个元素将保留在第一个位置，除非它与某些东西交换。只有在第一次扫描期间的任何时候比较出现+1(或-1，取决于内部结构)时才会发生这种情况。所有比较返回不同值的概率是 (2/3)^n-1，这与 1/n 不同。事实上，一旦完成排序，序列中的第一个元素出现在最前面的可能性在天文数字上是不可能的。因此，即使算法将终止，也不能保证您获得均匀随机分布。

如果您尝试使用快速排序、堆排序或合并排序之类的算法，那么算法最终会终止，但我不确定它是否保证是随机的。我会考虑一下这是否是均匀随机的，然后更新我的答案。

希望这对您有所帮助!