问题标签 [quicksort]

我在一次采访中被问到这个问题。它们都是 O(nlogn)，但大多数人使用 Quicksort 而不是 Mergesort。这是为什么？

在实现快速排序时，您必须做的一件事就是选择一个枢轴。但是当我看下面这样的伪代码时，我不清楚我应该如何选择枢轴。列表的第一个元素？还有什么？

有人可以帮我理解选择支点的概念，以及不同的场景是否需要不同的策略。

昨天我正在努力实现一个快速排序，然后我运行它，期望比 Mergesort 更快的运行时间（我也实现了）。我运行了这两个，虽然快速排序对于小于 100 个元素的较小数据集更快（并且我确实验证了它的工作原理），但合并排序很快成为更快的算法。有人告诉我，快速排序几乎总是比归并排序“更快”，而且我知道关于这个话题存在一些争论，但我至少预计它会比这更接近。对于 >10000 个元素的数据集，合并排序的速度提高了 4 倍以上。这是意料之中的，还是我的快速排序代码中有错误？

合并排序：

快速排序：

有谁知道完整的技术词汇来描述所有不同版本的快速排序？

我知道的一个是“胖枢轴”[A]（其中与枢轴匹配的所有项目都放置在子数组的中间，并被排除在进一步的排序之外）。

我想知道的是，当一个元素（枢轴）放在中间并从排序[B] 中排除时，以及零元素放在中间[C] 的位置。

下面是每个分区的示例：
输入子数组是 5,3,2,9,5,7
[A] 给出 [3,2],5,5,[9,7]
[B] 给出 [3,2 ],5,[9,5,7]
[C] 给出 [3,2,5],[9,5,7]

我想检查这是否是 QuickSort 的正确实现，它似乎在做这项工作，但我错过了什么吗？

}

固定的：

我正在考虑使用 GLSL 着色器将大量处理移植到 GPU。我偶然发现的一个直接问题是，在其中一个步骤中，算法需要维护一个元素列表，对它们进行排序并取几个最大的元素（哪个数字取决于数据）。在 CPU 上，这只是使用 STL 向量和 qsort() 来完成，但在 GLSL 中我没有这样的设施。有没有办法解决这个缺陷？

快速排序的最坏情况性能为 O(n ² )，但无论如何在实践中仍然广泛使用。为什么是这样？

我对 List Sort 方法如何处理排序有疑问。给定以下元素：

如果我尝试这样排序：

那么第一个元素就是之前的第二个元素“Second”。或者，换句话说，这个断言失败了：

当元素基本相同时，为什么 .NET 会重新排序我的列表？如果比较返回非零值，我希望它只对列表重新排序。

什么是具有 3 路分区的 QuickSort？

我认为 QuickSort 在某些特定情况下可能会导致堆栈溢出异常。

在排序过程中有两种选择枢轴元素的基本方法 - 枢轴值可以是排序范围中间的元素或随机选择的元素（在排序范围内）。第二种方法（随机）是否比第一种方法更不容易发生堆栈溢出？你能告诉我吗？

这是我的快速排序（Delphi）版本：

提前感谢您的建议！

马吕斯。