php快速排序的三种实现（吊打面试官）

水深无声 2022-06-07 07:13 141阅读 0赞

php这个语言很有意思，通过数组合并就可以“偷懒”实现快速排序，233333

相比较python的缜密和巧妙，这个方法可以说很不要脸了

具体实现代码如下，有时间补一个有完整的数值交换过程的代码

public function quickSort($data)
    {
        $size = count($data);
        if($size>1) {
            $key = $data[0];
            $l = $r = [];
            for ($i = 1; $i < $size; $i++) {
                if ($data[$i] >= $key)
                    $r[] = $data[$i];
                else
                    $l[] = $data[$i];
            }
            $l_re = quickSort($l);
            $r_re = quickSort($r);
    
            return array_merge($l_re, [$key], $r_re);
        }
        else
            return $data;
    }

补上有数值交换过程的代码，效率可能不及上面，重在过程理解

public function quickSortReal($data)
    {
        $size = count($data);
        if($size>1)
        {
            $key = $data[0];
            $i = 0;
            $j = $size-1;
            while($i<$j)
            {
                while($i<$j && $data[$j]>=$key)
                    $j--;
                $data[$i] = $data[$j];
                $data[$j] = $key;//用于交换数值,但是后面又会被覆盖,所以该行代码没有多大意义
                while($i<$j && $data[$i]<=$key)
                    $i++;
                $data[$j] = $data[$i];
                $data[$i] = $key;
            }
            if($i == 0)
                $l = [];
            else
                $l = quickSortReal(array_slice($data,0,$i));
            if($i == $size-1)
                $r = [];
            else
                $r = quickSortReal(array_slice($data,$i+1,$size+1-$i));
            return array_merge($l,[$key],$r);
    
        }else
            return $data;
    
    }

第一种方法取巧，第二种方法中规中矩，还有第三种方法，可以说比较有技巧了，利用php的引用，一个数组就能完成整个排序过程，不用生成很多过程数组，很大程度的降低了运行内存，提高了代码效率，有空我会补上代码。

补上第三种方法，看着舒服多了

public function quickSortRefer(&$data,$start,$end)
    {
        $i = $start;
        $j = $end;
        if($i >= $j)
            return $data;
        else
            $key = $data[$i];
            while($i<$j)
            {
                while($i<$j && $data[$j] >= $key)
                    $j--;
                $data[$i] = $data[$j];
                $data[$j] = $key;//无用功的一行代码 数值交换 可以注释掉
                while($i<$j && $data[$i] <= $key)
                    $i++;
                $data[$j] = $data[$i];
                $data[$i] = $key;
            }
        $this->quickSortRefer($data,0,$i-1);
        $this->quickSortRefer($data,$i+1,$end);
    
        return $data;
    
    }

目前只想到这三种，欢迎补充