qsort是否要求进行一致的比较,还是可以将其用于改组？

Question

更新:请在不好的想法下提交.生活中没有任何免费的东西,这肯定是证据.一个简单的想法变坏了.然而,这绝对是值得学习的东西.

懒惰的编程挑战.如果我传递一个50-50为qsort的比较函数返回true或false的函数,我认为我可以有效地取消编写3行代码的结构数组.

int main ( int argc, char **argv)
{
    srand( time(NULL) );  /* 1 */
    ...
    /* qsort(....) */     /* 2 */
}

...

int comp_nums(const int *num1, const int *num2)
{
    float frand = 
          (float) (rand()) / ((float) (RAND_MAX+1.0));  /* 3 */

    if (frand >= 0.5f)
         return GREATER_THAN;
    return LESS_THAN;
}

我需要寻找的任何陷阱？是否可以通过交换更少的线路,或者这对于3条非平凡的线路来说是最干净的？

Answer 1

馊主意.我的意思是非常糟糕.

您的解决方案会产生不可预测的结果,而不是随机结果,并且存在很大差异.你不知道随机比较的qsort会做什么,以及所有组合是否同样可能.这是洗牌的最重要标准:所有组合必须具有相同的可能性.有偏见的结果等同于大麻烦.在你的例子中没有办法证明这一点.

你应该实现Fisher-Yates shuffle(也称为Knuth shuffle).

Answer 2

除了其他答案之外,这比简单的Fisher-Yates shuffle更糟糕,因为它太慢了.qsort算法是O(n*log(n)),Fisher-Yates是O(n).

维基百科提供了一些更详细的信息,说明为什么这种"洗牌"通常不像Fisher-Yates方法那样有效:

与其他改组算法比较

Fisher-Yates shuffle效率很高; 实际上,它的渐近时间和空间复杂度是最优的.结合高质量无偏随机数源,也保证产生无偏的结果.与一些其他解决方案相比,它还具有以下优点:如果仅需要部分结果排列,则可以在中途停止,或者甚至重复停止和重新启动,根据需要逐步地生成排列.在具有快速内置排序算法的高级编程语言中,一种替代方法,其中要被混洗的集合的每个元素被分配一个随机数,然后根据这些数字对该集合进行排序,在实践中可能更快[尽管具有更差的渐近时间复杂度(O(n log n)对O(n)),但需要引用].像Fisher-Yates shuffle一样,如果正确实现,这种方法也会产生无偏的结果,并且可能更容忍随机数中的某些偏差.但是,必须注意确保所分配的随机数永远不会重复,因为排序算法通常不会在出现平局的情况下随机排序元素.在支持使用用户指定的比较函数进行排序的语言中已经看到一些用法的上述方法的变体是通过使用返回随机值的比较函数对列表进行排序来混洗列表.然而,这并不总是有效:对于许多常用的排序算法,由于排序实现中的内部不对称,结果最终会产生偏差.[7]

这链接到这里:

还有一件事在撰写本文时,我尝试了各种版本的方法,并在原始版本中发现了另一个缺陷(由我重命名shuffle_sort).当我说"每次调用时它返回一个很好的洗牌数组时,我错了."

结果并没有很好地改组.他们有偏见.厉害.这意味着元素的某些排列(即排序)比其他元素更可能.这是另一个代码片段来证明它,再次借鉴新闻组的讨论:

N = 100000
A = %w(a b c)
Score = Hash.new { |h, k| h[k] = 0 }
N.times do
  sorted = A.shuffle  
  Score[sorted.join("")] += 1
end

Score.keys.sort.each do |key|
  puts "#{key}: #{Score[key]}"
end

此代码将三个元素的数组混合100,000次:a,b,c并记录每个可能结果的实现次数.在这种情况下,只有六种可能的排序,我们应该每个约16666.66次.如果我们尝试shuffle (shuffle或shuffle_sort_by)的无偏见版本,结果如预期:

 
 abc: 16517
 acb: 16893
 bac: 16584
 bca: 16568
 cab: 16476
 cba: 16962

当然,存在一些偏差,但它们不应超过预期值的百分之几,并且每次运行此代码时它们应该不同.我们可以说分布是均匀的.

好的,如果我们使用shuffle_sort方法会发生什么？

 abc: 44278 
 acb: 7462
 bac: 7538
 bca: 3710
 cab: 3698
 cba: 33314

这根本不是均匀分布.再次？

它显示了排序方法的偏差,并详细说明了为什么会这样.最后,他链接到Coding Horror:

让我们来看看正确的Knuth-Fisher-Yates shuffle算法.

for (int i = cards.Length - 1; i > 0; i--)
{
  int n = rand.Next(i + 1);
  Swap(ref cards[i], ref cards[n]);
}

你看得到差别吗？我第一次错过了它.比较3卡套牌的掉期:

 
Naïve shuffle   Knuth-Fisher-Yates shuffle
rand.Next(3);    rand.Next(3);
rand.Next(3);    rand.Next(2);
rand.Next(3); 

天真的洗牌导致3 ^ 3(27)种可能的套牌组合.这很奇怪,因为数学告诉我们真的只有3个!或3张牌组的6种可能组合.在KFY shuffle中,我们从初始订单开始,从第三个位置与三个卡中的任何一个交换,然后从第二个位置再次与剩余的两个卡交换.