我在网上学习快速排序时发现了很多变体方法。
每次在左/右指针交叉后的"替换/交换枢轴位置"阶段都会让我感到困惑。
问题：每轮后将枢轴替换为左/右指针位置。 这就是问题所在。
抱歉，我找不到合适的示例，因为我无法解决我的问题。 但是，如果有人有更好的示例以及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
试图帮助你使问题更容易理解
考虑包含 N 个元素的数组的此类场景：
第 1 阶段：选择一个枢轴。(例如，随机指数或三中位数(
第 2 阶段：将枢轴放在某个位置。例如，在枢轴索引处与最后一个元素交换价值。Pivot 现在正在A[N-1]
第 3 阶段：分离除枢轴(最后一个位置(以外的所有元素 - 较小的元素在A[0]..A[l]中，较大的元素在A[r]..A[N-2]
第 4 阶段：交换枢轴 ( A[N-1] ( 与A[r]
什么阶段不清楚？
Q#1：是否强制阶段 2 通过将其交换在第一个/最后一个位置来放置枢轴？ 因为我没有在每个示例中都找到它。 有些地方它留在那里，在第 1 轮之后，它用向上/向下指针交换它的位置。
如果使用第一个或最后一个元素作为透视，则无需交换它，否则必须交换。请注意，pivot=first 是选择枢轴的最简单方法，但最坏情况的概率太高 - 对于(几乎(排序数组]
Q#2：让我们也讨论一下内存
快速排序不需要额外的内存来存储新阵列，它可以就地工作。递归实现在堆栈中占用一些内存(隐式(。
用 A[r] 替换枢轴意味着第一轮后的右(下(指针位置，对吧？
是的，它是交叉过程中的向下指针位置。注意 - 当枢轴在结束时与向下指针交换，但当枢轴在开始时与向上指针交换。
第三阶段 怎么分开的？
使用分区方案维基。考虑霍尔的分区 - 它更容易理解。
排序的PHP代码：(我认为使用Lomuto分区方案(
<?php
$unsorted = array(43,21,2,1,9,24,2,99,23,8,7,114,92,5);
function quick_sort($array)
{
// find array size
$length = count($array);
// base case test, if array of length 0 then just return array to caller
if($length <= 1){
return $array;
}
else{
// select an item to act as our pivot point, since list is unsorted first position is easiest
$pivot = $array[0];
// declare our two arrays to act as partitions
$left = $right = array();
// loop and compare each item in the array to the pivot value, place item in appropriate partition
for($i = 1; $i < count($array); $i++)
{
if($array[$i] < $pivot){
$left[] = $array[$i];
}
else{
$right[] = $array[$i];
}
}
// use recursion to now sort the left and right lists
return array_merge(quick_sort($left), array($pivot), quick_sort($right));
}
}
$sorted = quick_sort($unsorted);
print_r($sorted);
?>
//RESULT: Array ( [0] => 1 [1] => 2 [2] => 2 [3] => 5 [4] => 7 [5] => 8 [6] => 9 [7] => 21 [8] => 23 [9] => 24 [10] => 43 [11] => 92 [12] => 99 [13] => 114 )