在快速排序中，想法是您不断选择一个支点。并且您将在左侧找到的大于枢轴的值与您在右侧找到的小于枢轴的值交换。见：参考
只想 100% 确定在以下情况下会发生什么：
- 左边没有值大于枢轴，右边没有值小于枢轴
- 左边的值大于枢轴，右边没有值小于枢轴
- 左边没有值大于枢轴，右边没有值小于枢轴
问问题
788 次
2 回答
0
交换标准取决于实现。您提到的三种情况会发生什么取决于分区方案。快速排序有很多实现，但主要的两个最著名的（在我看来）是：
Hoare 分区：第一个元素是枢轴，两个索引变量 (
i和j) 将数组 (a[]) 向中心移动，而它们遇到的元素小于/大于枢轴。然后a[j]和a[i]被交换。请注意，在此实现中，交换发生在等于 pivot的元素上。当您的数组包含许多相同的条目时，这被认为很重要。Afteriandjcross,a[0]与 交换a[j]，因此枢轴在较小或等于分区和较大或等于分区之间移动。洛穆托的分区。这是在“就地版本”下的当前 Wiki 快速排序条目中以伪代码实现的一种。这里的 pivot 可以是任何东西（比如一个中位数，或者三个的中位数），并与 . 的最后一个元素交换
a。这里只i“走”向数组的末尾：每当a[i]>=pivot它被交换a[j]并j递减时。最后，枢轴与a[i+1]
（例如，请参见此处的插图）。
Robert Sedgewick 提倡一种三向分区方案，其中数组被分成三个分区：小于、等于和大于枢轴：声称它在具有大量重复值或相同值的数组上具有更好的性能。它的实现方式有所不同（请参阅上面的链接）。
于 2013-04-02T02:38:45.593 回答
0
虽然枢轴值的选择对性能很重要，但对排序并不重要。
一旦选择了某个值作为枢轴，然后将所有小于或等于枢轴的值移动到枢轴的左侧，然后将所有大于枢轴的值移到其右侧。
在所有这些移动之后，枢轴值处于其最终位置。
然后，您对枢轴值左侧的子数组以及其右侧的子数组递归地重复上述过程。或者当然，如果子数组中包含 0 或 1 个元素，则与它们无关，无需排序。
因此，通过这种方式，您最终会选择一堆枢轴值，这些枢轴值会在所有移动之后进入它们的最终位置。在这些枢轴值之间是空的或单个元素的子数组，不需要如前所述进行排序。
于 2013-03-30T13:08:18.767 回答