PHP – 快速排序 – 老迟笔记

一、概述

快速排序是一种非常高效的排序算法，它采用“分而治之”的思想，把大的问题拆分为小的问题，小的问题再拆分为更小的问题。

1、原理：

通过设置一个初始中间值，来将需要排序的数组分成3部分，小于中间值的左边，中间值，大于中间值的右边，继续递归用相同的方式来排序左边和右边，最后合并数组

二、PHP 代码实现

<?php
declare(strict_types = 1);

class TestCase
{
    /**
     * 快速排序
     *
     * @param array $array
     * @return array
     */
    public function sortArray(array $array) : array
    {
        if (count($array) <= 1) {
            return $array;
        }
        // 数组长度
        $arrayLen = count($array);
        // 以第一个元素作为中间值
        $middle = $array[0];
        // 初始化 接收小于中间值的数组 和 接收大于中间值的数组
        $left = $right = [];

        // 循环比较
        for ($i = 1; $i < $arrayLen; $i++) {
            if ($middle < $array[$i]) {
                $right[] = $array[$i];
            } else {
                $left[] = $array[$i];
            }
        }
        // 递归排序划分好的2边
        $left = $this->sortArray($left);
        $right = $this->sortArray($right);
        return array_merge($left, [$middle], $right);
    }

}

// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
$arrObject = new TestCase();
// 执行排序
$arr = $arrObject->sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}

// 结果
3 15 15 19 20 22 24 36 36 64 77 95

三、说明

　　快速排序是通过分治递归实现的，如果分割出的子序列长度很小（小于20）的话，那么通常递归的排序效率就没有插入排序或希尔排序那么快了。

　　因此，使用快速排序前，可以先判断数组的长度，如果小于10的话，可以直接使用插入排序，而不是递归调用的快速排序。

四、算法性能分析

最好情况：T(n) = O(nlog₂ⁿ)

最差情况：T(n) = O(n²)

平均情况：T(n) = O(nlog₂ⁿ)

打赏赞