qsort是否要求进行一致的比较，还是可以将其用于改组？
更新 ：请在糟糕的想法下提交。 生活中没有任何免费的东西，这肯定是证据。 一个简单的想法变坏了。 然而，这绝对是值得学习的东西。
懒惰的编程挑战。 如果我传递一个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条非平凡线路来说是最干净的？
馊主意。 我的意思是非常糟糕。
您的解决方案会产生不可预测的结果，而不是随机结果，并且存在很大差异。 你不知道具有随机比较的qsort会做什么以及所有组合是否同样可能。 这是洗牌的最重要标准：所有组合必须具有相同的可能性。 有偏见的结果等同于大麻烦。 在你的例子中没有办法certificate这一点。
你应该实现Fisher-Yates shuffle （也称为Knuth shuffle）。
除了其他答案之外，这比简单的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）。 当我说“每次调用它都会返回一个很好的混乱数组”时，我错了。结果并没有很好地改组。 他们有偏见。 厉害。 这意味着元素的某些排列（即排序）比其他元素更可能。 这是另一个代码片段来certificate它，再次借鉴新闻组的讨论：
N = 100000 A = %w(abc) 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 驾驶室：16476 cba：16962
当然，存在一些偏差，但它们不应超过预期值的百分之几，并且每次运行此代码时它们应该不同。 我们可以说分布是均匀的。
好的，如果我们使用shuffle_sort方法会发生什么？
abc：44278 acb：7462 bac：7538 bca：3710 驾驶室：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随机洗牌Knuth-Fisher-Yates洗牌 rand.Next（3）; rand.Next（3）; rand.Next（3）; rand.Next（2）; rand.Next（3）;
天真的洗牌导致3 ^ 3（27）种可能的套牌组合。 这很奇怪，因为数学告诉我们真的只有3个！ 或3张牌组的6种可能组合。 在KFY shuffle中，我们从初始订单开始，从第三个位置与三个卡中的任何一个交换，然后从第二个位置再次与剩余的两个卡交换。
不，这不会正确地改组arrays，它几乎不会在原始位置周围移动元素，具有指数分布。
比较函数不应该返回一个布尔类型，它应该返回一个负数，一个正数或零， qsort()用它来确定哪个参数大于另一个。
旧新事物就是这个
我认为在向下的过程中递归地随机分区集合的基本思想并在上行路径中连接结果将起作用（它将平均O（n * log n）二进制决策并且接近log2（事实（n））但是q-sort不一定会用随机谓词来做。
BTW我认为对于任何O（n * log n）排序策略都可以说同样的论点和问题。
兰德不是那里最随机的东西……如果你想洗牌或其他东西，这不是最好的。 另外一个Knuth shuffle会更快，但如果它不会永远循环你的解决方案是好的