php - QuickSort:当 Pivot 交换位置时无法理解部分

Question

我在网上学习快速排序时发现了很多变体方法。

每次在左/右指针交叉后，在“替换/交换枢轴位置”阶段让我感到困惑。

问题:在每轮之后将枢轴替换为左/右指针位置。这就是问题所在。

抱歉，我找不到合适的例子，因为我无法用它来解决我的问题。但如果有人有更好的示例以及它的 PHP 代码，请问？

示例:[81,70,97,38,63,21,85,68,76,9,57,36,55,79,74,85,16,61,77,49,24]采取支点:57

如果需要可以拿这个例子: https://ece.uwaterloo.ca/~cmoreno/ece250/quick-sort-complete-example.pdf

Answer 1

试图帮助你使问题更容易理解

考虑具有 N 个元素的数组的这种情况:

第 1 阶段:选择一个支点。 (例如，随机索引或三中位数)

第 2 阶段:将枢轴放在某个位置。例如，将枢轴索引处的值与最后一个元素交换。枢轴现在位于 A[N-1]

阶段 3:分离所有元素，但不包括枢轴(最后位置)- 较小的元素在 A[0]..A[l] 中，较大的元素在 A[r] 中。 .A[N-2]

阶段 4:交换枢轴 (A[N-1]) 与 A[r]

什么阶段不清楚？

Q#1: is it mandatory stage 2 to put the pivot by swapping it at first/last position? because i didn't found it in every example. some where it remains there and after 1st round it swaps it position with up/down pointer.

如果使用第一个或最后一个元素作为基准，则不需要交换它，否则交换是强制性的。请注意，pivot=first 是选择主元的最简单方法，但最坏情况的概率太高 - 对于(几乎)排序数组]

Q#2: let's discuss about the memory too

QuickSort 不需要额外的内存用于新数组，它就地工作。递归实现占用堆栈中的一些内存(隐式)。

replacing the pivot with the A[r] means the right(down) pointer position after 1st round, right?

是的，穿越的时候是向下的指针位置。注意 - 当枢轴结束时与向下指针交换，但当枢轴在开始时与向上指针交换。

stage 3 How did it Separated?

使用分区方案 Wiki .考虑 Hoare 的分区 - 它更容易理解。