快速排序_单向扫描法

关键词：

• p: 主元
• scan_pos: 扫描指针
• bigger: 右侧指针

思路

• 用两个指针将数组划分为三个区间，
• 扫描指针(scan_pos)左边是确认小于等于主元的，扫描指针到某个指针(next_bigger_pos)中间为未知的，因此我们将第二个指针(next_bigger_pos)成为位未知区间末指针，末指针的右边区间为确认大于主元的元素。

结构图

边界分析

• <= sp 右移，> 交换，bigger左移
• 如果最后一个元素大于主元，bigger左移之后小于scanner
• 如果最后一个扫描元素小于主元，scanner的右移导致，scanner大于bigger

PHP代码示例

class quickSort {

    function sort() 
    {
        $arr = [4, 6, 2, 9, 1, 5, 7, 8];
        $this->qsort($arr, 0, count($arr) - 1);
        print_r($arr);
    }

    function qsort(&$arr, $low, $right) 
    {
        if ($low < $right) {
            $q = $this->partition($arr, $low, $right);
            $this->qsort($arr, $low, $q-1);
            $this->qsort($arr, $q+1, $right);
        }
    }

    //单向扫描
    function partition(&$arr, $low, $right) 
    {
        $pivot = $arr[$low]; //主元,默认数组第一个
        $sp = $low + 1;      //扫描指针
        $bigger = $right;    //右侧指针
        while ($sp <= $bigger) {
            if ($arr[$sp] <= $pivot) {
                $sp++;
            } else {
                $this->swap($arr, $sp, $bigger);
                $bigger--;
            }
        }
        $this->swap($arr, $low, $bigger);//高低位互换
        return $bigger;
    }

    function swap(&$arr, $i, $j) 
    {
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
    }
}

$obj = new quickSort();
$obj->sort();

结果

Array
(
    [0] => 1
    [1] => 2
    [2] => 4
    [3] => 5
    [4] => 6
    [5] => 7
    [6] => 8
    [7] => 9
)

流程分析

• 主元 >= sp，sp右移
• 主元 < sp，sp和bigger交换，bigger左移