问题标签 [quicksort]

在分析 QS 时，每个人总是提到“几乎排序”的最坏情况。自然输入何时会出现这种情况？

我想出的唯一例子是重新索引。

快速排序和堆排序都进行就地排序。哪个更好？哪些应用和案例是首选？

i'm trying to profile a quicksort code. the code is as follows:

please help me out!

有可能在 Scala 中做这种事情吗？

I'm trying to implement quicksort in a functional style using C# using linq, and this code randomly works/doesn't work, and I can't figure out why.
Important to mention: When I call this on an array or list, it works fine. But on an unknown-what-it-really-is IEnumerable, it goes insane (loses values or crashes, usually. sometimes works.)
The code:

Can you find any faults here that would cause this to fail?

Edit: Some better test code:

我有一个关于快速排序算法的问题。我实现了快速排序算法并播放它。初始未排序数组中的元素是从一定范围内选择的随机数。我发现随机数的范围会影响运行时间。例如，从 (1 - 2000) 范围内选择的 1, 000, 000 随机数的运行时间需要 40 秒。如果从范围（1 - 10,000）中选择 1,000,000 数字，则需要 9 秒。但我不知道如何解释。在课堂上，我们讨论了枢轴值可以影响递归树的深度。
对于我的实现，数组的最后一个值被选为枢轴值。我不使用随机方案来选择枢轴值。

我正在阅读 M.Mitzenmacher 和 E.Upfal 的“概率与计算”。我在理解如何计算两个元素的比较概率时遇到问题。

输入：数字的排序列表 (y1,y2,...,yN)。我们正在寻找枢轴元素（随机）。问题：比较两个元素 yi 和 yj (j>i) 的概率是多少？

答案（来自书本）：如果 yi 或 yj 将在序列 (yi,yi+1,...,yj-1,yj) 的第一次抽奖中被选为枢轴，则将比较 yi 和 yj。所以概率是：2/(j-i+1)。

对我来说，问题是最初的主张：例如，从整个列表中的第一次抽签中选择 yi 将导致与 yj 的比较（反之亦然），概率为 2/n。

因此，相反，“反向”声明是正确的——在 yi 或 yj 之前不能选择 (yi+1,...,yj-1) 元素，但“池”大小不固定（在第一次抽奖中）它肯定是 N，但第二个它更小）。

有人可以解释一下作者是如何得出如此简单的结论的吗？

Edit1：一些好人完善了我的帖子，谢谢:-)。

Edit2：列表最初是排序的。

快速排序和调优快速排序之间的根本区别是什么？快速排序有哪些改进？Java 如何决定使用它而不是归并排序？

显然 LINQ 的“OrderBy”最初被指定为不稳定的，但到了 Orca 的时候它被指定为稳定的。并非所有文档都已相应更新 - 请考虑以下链接：

• Jon Skeet 谈 OrderBy 稳定性
• Troy Magennis on OrderBy 稳定性

但是如果 LINQ 的 OrderBy 现在是“稳定的”，那么这意味着它没有使用快速排序（本质上是不稳定的），即使某些文档（例如 Troy 的书）说它是。所以我的问题是：如果不是快速排序，那么 LINQ 的 orderBy 使用的实际算法是什么？

我正在研究 GenericList 类中的递归 QuickSort 方法实现。我将有第二种方法，它接受 compareDelegate 来比较不同的类型，但出于开发目的，我对 GenericList< int> 进行排序。

我根据列表大小在不同的地方接收 stackoverflow 区域。

我已经盯着和跟踪这段代码几个小时了，可能只需要一双新的（更有经验的）眼睛。我绝对想知道它为什么坏了，而不仅仅是如何修复它。

完成的产品：