快速排序算法

快速排序

理解：

快速排序两个关键点：选取基准和mark指针
基准循环不变，基准与数组元素比较，满足条件mark指针进位交换 ，mark指针指定的元素值一定小于或者等于基准值（当从小到大排时）
最后交换基准和mark指针元素，将数组切割，递归重复上述过程

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。

image.png
这种思路就叫作分治法。
具体如何实现呢？有两种方法。
1. 双边循环法。
2. 单边循环法。

单边循环法比双边循环更容易理解和运用，这里只介绍单边循环法
首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界。

image.png

接下来，从基准元素的下一个位置开始遍历数组。
如果遍历到的元素大于基准元素，就继续往后遍历。
如果遍历到的元素小于基准元素，则需要做两件事：第一，把mark指针右移1位，因为小于pivot的区域边界增大了1；第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。首先遍历到元素7，7>4，所以继续遍历。

image.png
接下来遍历到的元素是3，3<4，所以mark指针右移1位。
image.png
随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。
image.png
image.png

按照这个思路，继续遍历，后续步骤如图所示。

image.png

具体代码运用了递归
详情如下:

class Code{
    
    function quickSort(&$arr,$intStart,$intEnd){
        // 递归结束条件：startIndex大于或等于endIndex时
        if($intStart >= $intEnd){
            return;
        }
        // 根据基准元素，分成两部分进行递归排序
        $mark = $this->positionMark($arr,$intStart,$intEnd);
        // 根据基准元素，分成两部分进行递归排序
        $this->quickSort($arr,$intStart,$mark-1);
        $this->quickSort($arr,$mark+1,$intEnd);
    }

    /**
    * 分治（单边循环法）
    * @param arr 待交换的数组
    * @param intStart 起始下标
    * @param intEnd 结束下标
    */
    function positionMark(&$arr,$intStart,$intEnd){
        //以数组首位作为基准
        $base = $arr[$intStart];
        //mark起始为数组首位
        //mark指针的作用就是使mark指针的左边小于等于基准，右边大于基准
        $mark = $intStart;
        //遍历数组从基准的后一位与基准对比，直到数组的最后一个
        for($i=$intStart+1;$i<=$intEnd;$i++){
            //因为是从小到大排序
            //故如果比基准小，元素与mark下标值互换，移动到左边
            if($arr[$i] < $base){
                //mark标记的值永远小于或者等于基准值的
                //mark向前移动一位则是大于基准值的，发生交换则是把大值换到后边，小值放到前边
                $mark++;
                $tmp = $arr[$mark];
                $arr[$mark] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
        //最后替换基准和mark
        $arr[$intStart] = $arr[$mark];
        $arr[$mark] = $base;

        return $mark;
    }

    //运行
    function run(){
        $arr = array(8,5,7,4,2,0,1,3,9);
        $this->quickSort($arr,0,count($arr)-1);
        print_r($arr);
    }
    
}
$obj = new Code();
$obj->run();

输出结果：

image.png