快速排序-双向扫描法

思路

单向扫描是第一个指针sp从左往右扫,遇到小的则下移一位,然后sp++，
遇到大的交换该值与第二个指针bigger的值,然后bigger–；
双向扫描分区法

• 设置两个扫描指针 sp 和 bigger,两个指针同时往中间扫；
• sp遇到比主元小的元素则移动到下一位，遇到比主元大的元素则暂停移动
• bigger遇到比主元大的元素则移动到前一位，遇到比主元小的元素则暂停移动
• sp和bigger都暂停后，交换两个指针所指向的值
• 主元的选取还是选取范围内的第一个元素
• 与单向扫描法一样，扫描结束时sp和bigger 指针会交错，sp指针指向第一个比主元大的元素，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) {
            //从左往右扫描
            while ($sp <= $bigger && $arr[$sp] < $pivot) {
                $sp++;
            }
            //从右往左扫描
            while($sp <= $bigger && $arr[$bigger] > $pivot) {
                $bigger--;
            }
            //交换位置
            if ($sp < $bigger) {
                $this->swap($arr, $sp, $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
)