• 周日. 6 月 16th, 2024

    排序算法-快速排序

    root

    3 月 9, 2021 #快速排序, #算法
    算法算法

    快速排序是对冒泡排序算法的一种改进。

    基本思想:通过一趟排序将要排序的数组分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据小,然后再按此方法对两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序。

    快速排序平均算法时间复杂度为O(nlogn),它最坏的情况为O(n^2).

    代码实现

    方法一:

    function quickSort($arr) {
        $count = count($arr);
        if ($count<2) {
            return $arr;
        }
        //创建临时数组,以基准值为分界线,大于基准值的放在右侧,
        //小于基准值的放在左侧
        $leftArr = $rightArr = [];
        //基准值, 一般取数组第一个元素
        $middle = $arr[0];
        for($i=1;$i<$count; $i++) {
            if ($arr[$i]<$middle) {
                $leftArr[] = $arr[$i];
            } else {
                $rightArr[] = $arr[$i];
            }
        }
        //递归,将左右数组排序
        $leftArr = quickSort($leftArr);
        $rightArr = quickSort($rightArr);
        //将排好序的临时数组合并
        return array_merge($leftArr,[$middle],$rightArr);
    }

    方法二:

    function quick_sort($arr) {
        $count = count($arr);
        if($count<2) {
            return $arr;
        }
        $i = 0;
        $j = $count - 1;
        //基准值
        $key = $arr[0];
        while($i<$j) {
            //首先从后往前比较,比基准值大的放过,比基准值小的做交换
            while($i<$j && $arr[$j]>=$key) {
                $j--;
            }
            //交换
            $arr[$i] = $arr[$j];
            $arr[$j] = $key;
            //再从前往后比较,比基准值小的放过,比基准值大的做交换
            while($i<$j && $arr[$i] <= $key) {
                $i++;
            }
            $arr[$j] = $arr[$i];
            $arr[$i] = $key;
        }
        //经过一轮交换,基准值左侧全部比基准值小,基准值右侧比基准值大,但左右两侧并不一定是排好序的,
        //然后进行递归,将基准值左右两侧进行排序
        if ($i==0) {
            $left = [];
        } else {
            $left = quick_sort(array_slice($arr,0,$i));
        }
        if($i == $count-1) {
            $right = [];
        } else {
            $right = quick_sort(array_slice($arr, $i+1, $count+1-$i));
        }
        //将排好序的数组进行合并返回
        return array_merge($left, [$key], $right);
    }

    root