PHP实现快速排序算法

快速排序是对冒泡排序的一种改进,实现过程是通过一趟排序将数据分割成两部分,其中一部分数据都要比另一部分数据要小,然后通过递归的方式对两部分数据继续进行排序分割,直至数据有序。

网络上寻找php实现快速排序时,基本都是循环时比对基数,按大小生成两个新的数组,然后将递归结果进行array_merge,这种处理虽然简单,但没有体现出快速排序位置交换的精髓…第一个人写出点东西,诸位博主连想都不想直接疯狂转载,你们为什么不直接使用sort排序呢,一行就够了…
学习的过程中查阅资料总是被各种坑爹,以下是快速排序的实现代码,本人水平有限,献丑。

<?php
$array = [4,3,9,5,2,8,7,6,1];
$left = 0;
$right = count($array)-1;
function quick_sort(&$array ,$left, $right) {
    //左下标小于等于右下标,确保数组有效
    if ($left >= $right ){
        return;
    }
    //声明基数
    $tmp = $array[$left];
    //声明i,j
    $i = $left;
    $j = $right;
    //左<-右,左->右循环比对基数
    while ($i != $j){
        //左<-右寻找小于基数的值的下标
        while ($i < $j && $array[$j] >= $tmp){
            $j--;
        }
        //左->右寻找大于基数的值的下标
        while ($i < $j && $array[$i] <= $tmp){
            $i++;
        }
        //i和j没有相遇,交换i和j位置的值
        if ($i < $j){
            $itmp = $array[$i];
            $array[$i] = $array[$j];
            $array[$j] = $itmp;
        }
    }
    //i和j相遇后,代表j的右侧已经没有比基数小的值,则基数和i/j位置交换
    if ($left < $i){
        $array[$left] = $array[$i];
        $array[$i] = $tmp;
    }
    //以i和j相遇处为分割点,将数组分成两部分继续排序
    //因为,当i和j相遇并和基数交换位置后,相遇位置左侧一定都小于基数,相遇位置右侧一定都大于基数,所以可以分开递归
    quick_sort($array,$left,$i-1);
    quick_sort($array,$i+1,$right);
}
quick_sort($array, $left, $right);
echo "排序结果:".implode(",",$array);

输出

排序结果:1,2,3,4,5,6,7,8,9

我们将代码执行过程echo出来,理解下位置交换和分割的过程

<?php
$array = [4,3,9,5,2,8,7,6,1];
$left = 0;
$right = count($array)-1;
echo "key:数组索引\n";
echo "left:数组开始元素下标\n";
echo "right:数组结尾元素下标\n";
echo "i:左->右对比时元素下标\n";
echo "j:左<-右对比时元素下标\n";
echo "\r\n\r\n\r\n";
function quick_sort(&$array ,$left, $right) {
    //左下标小于等于右下标,确保数组有效
    if ($left >= $right ){
        return;
    }
    $debugs = array();
    $debugs[] = "key区间:".$left.",".$right;
    $debugs[] = "当前区间元素列表:".implode(",",array_slice($array, $left, $right - $left + 1));
    //声明基数
    $tmp = $array[$left];
    $debugs[] = "从左侧取基数:left({$left})={$tmp}";
    //声明i,j
    $i = $left;
    $j = $right;
    //左<-右,左->右循环比对基数
    while ($i != $j){
        //左<-右寻找小于基数的值的下标
        while ($i < $j && $array[$j] >= $tmp){
            $j--;
        }
        //左->右寻找大于基数的值的下标
        while ($i < $j && $array[$i] <= $tmp){
            $i++;
        }
        //i和j没有相遇,交换i和j位置的值
        if ($i < $j){
            $debugs[] = "左<-右找小于{$tmp},找到j({$j})={$array[$j]},左->右找大于{$tmp}找到i({$i})={$array[$i]},交换位置";
            $itmp = $array[$i];
            $array[$i] = $array[$j];
            $array[$j] = $itmp;
            $debugs[] = "元素列表:".implode(",",$array);
        }
    }
    //i和j相遇后,代表j的右侧已经没有比基数小的值,则基数和i/j位置交换
    if ($left < $i){
        $debugs[] = "i({$i})和j({$j})相遇,i({$i})={$array[$i]}右侧已无<{$tmp}元素,基数left({$left})={$tmp}和i({$i})={$array[$i]}交换位置";
        $array[$left] = $array[$i];
        $array[$i] = $tmp;
    }
    $debugs[] = "元素列表:".implode(",",$array);
    $debugs[] = "当前区间元素列表:".implode(",",array_slice($array, $left, $right - $left + 1));
    $debugs[] = "当前区间从i和j相遇处分成两段(".implode(",",array_slice($array, $left, $i - $left))."|".implode(",",array_slice($array, $i+1,$right - 1))."),递归处理";
    echo "####\n".implode("\n",$debugs);
    echo "\r\n\r\n\r\n";
    //以i和j相遇处为分割点,将数组分成两部分继续排序
    //因为,当i和j相遇并和基数交换位置后,相遇位置左侧一定都小于基数,相遇位置右侧一定都大于基数,所以可以分开递归
    quick_sort($array,$left,$i-1);
    quick_sort($array,$i+1,$right);
}
quick_sort($array, $left, $right);
echo "排序结果:".implode(",",$array);

执行代码,查看处理过程

key:数组索引
left:数组开始元素下标
right:数组结尾元素下标
i:左->右对比时元素下标
j:左<-右对比时元素下标



####
key区间:0,8
当前区间元素列表:4,3,9,5,2,8,7,6,1
从左侧取基数:left(0)=4
左<-右找小于4,找到j(8)=1,左->右找大于4找到i(2)=9,交换位置
元素列表:4,3,1,5,2,8,7,6,9
左<-右找小于4,找到j(4)=2,左->右找大于4找到i(3)=5,交换位置
元素列表:4,3,1,2,5,8,7,6,9
i(3)和j(3)相遇,i(3)=2右侧已无<4元素,基数left(0)=4和i(3)=2交换位置
元素列表:2,3,1,4,5,8,7,6,9
当前区间元素列表:2,3,1,4,5,8,7,6,9
当前区间从i和j相遇处分成两段(2,3,1|5,8,7,6,9),递归处理


####
key区间:0,2
当前区间元素列表:2,3,1
从左侧取基数:left(0)=2
左<-右找小于2,找到j(2)=1,左->右找大于2找到i(1)=3,交换位置
元素列表:2,1,3,4,5,8,7,6,9
i(1)和j(1)相遇,i(1)=1右侧已无<2元素,基数left(0)=2和i(1)=1交换位置
元素列表:1,2,3,4,5,8,7,6,9
当前区间元素列表:1,2,3
当前区间从i和j相遇处分成两段(1|3),递归处理


####
key区间:4,8
当前区间元素列表:5,8,7,6,9
从左侧取基数:left(4)=5
元素列表:1,2,3,4,5,8,7,6,9
当前区间元素列表:5,8,7,6,9
当前区间从i和j相遇处分成两段(|8,7,6,9),递归处理


####
key区间:5,8
当前区间元素列表:8,7,6,9
从左侧取基数:left(5)=8
i(7)和j(7)相遇,i(7)=6右侧已无<8元素,基数left(5)=8和i(7)=6交换位置
元素列表:1,2,3,4,5,6,7,8,9
当前区间元素列表:6,7,8,9
当前区间从i和j相遇处分成两段(6,7|9),递归处理


####
key区间:5,6
当前区间元素列表:6,7
从左侧取基数:left(5)=6
元素列表:1,2,3,4,5,6,7,8,9
当前区间元素列表:6,7
当前区间从i和j相遇处分成两段(|7,8,9),递归处理


排序结果:1,2,3,4,5,6,7,8,9

以上快速排序代码,要求数据不能重复,并且每次都以开头元素为基数,当i和j相遇后,和基数交换并分割成两部分继续递归处理,最终实现快速排序。