QuickSort：当 Pivot 交换位置时无法理解部分

Question

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

每次在 Left/Right 指针 被越过后 "Replacing/Swapping Pivot position" 阶段让我感到困惑。

问题：在每一轮之后用左/右指针位置替换枢轴。就是这个问题。

抱歉，我找不到合适的例子，因为我无法用它来回答我的问题。但是如果有人有更好的例子以及它的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 是选择 pivot 的最简单方法，但最坏情况的概率太高 - 对于（几乎）排序数组]

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 的分区 - 它更容易理解。

Answer 2

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 )

QuickSort：当 Pivot 交换位置时无法理解部分

QuickSort: Can't understand the part when the Pivot swaps its position

php

sorting

algorithm

pivot

quicksort