五、快速排序

原理

快速排序采用了和归并排序类似的分而治之的思想,归并排序中顺序的确定是在 中完成的,即在合并两个子数组时来确定顺序的。而快速排序是在 的时候就确定了顺序,合并两个子数组时只需顺序连接即可。

步骤

  1. 取原始数组下标 0 位置为分割点。
  2. 遍历原始数组,依据分割点将原始数组切分成 2 份,左边一份小于分割点, 右边另一份大于或等于分割点。
  3. 将左右数组传入递归函数继续分割,返回的数组按照 左数组 + 分割点 + 右数组 直接合并即可。

快速排序

代码

第一种实现方式:新建左右临时数组,根据分割点分拣数据,最后将 左数组 + 分割点 + 右数组 合并。

<?php declare(strict_types=1);

class Algorithm
{
    public function quickSort(array $s): array
    {
        $n = count($s);
        if ($n < 2) return $s;

        $left = $right = [];
        for ($i = 1; $i < $n; $i++) {
            if ($s[$i] < $s[0])
                $left[] = $s[$i];
            else
                $right[] = $s[$i];
        }

        $arr = $this->quickSort($left);
        $arr[] = $s[0];
        return array_merge($arr, $this->quickSort($right));
    }
}

第二种实现方式:直接在原数组中操作,设定左右索引来确定子数组范围,分割点初始在最左侧,通过和最右侧的数比较大小,然后再逐步缩小范围来实现分割点的居中,分割点居中的过程中,也实现了分割点左侧数据小于分割点,右侧数据大于分割点。和 第一种实现方式 相比节约了最后 左数组 + 分割点 + 右数组 的合并步骤,每层平均节约了 n/2 的循环。

<?php declare(strict_types=1);

class Algorithm
{
    public function quickSort(array $s): array
    {
        $this->sort($s, 0, count($s)-1);
        return $s;
    }

    public function sort(array &$s, int $a, int $b): void
    {
        if ($a >= $b) return;

        // 可以通过随机获取中间数来尽可能避免最坏的 O(n²) 时间复杂度
        // $r = rand($a, $b);
        // [$nums[$a], $nums[$r]] = [$nums[$r], $nums[$a]];

        $i = $a;
        $j = $b;
        $mi = true; // middle_is_i 的缩写,锚点是否是$i
        while ($i < $j) {
            if ($s[$i] > $s[$j]) {
                [$s[$i], $s[$j]] = [$s[$j], $s[$i]];
                $mi = !$mi;
            }
            $mi ? $j-- : $i++;
        }

        $m = $mi ? $i : $j;
        $this->sort($s, $a, $m-1);
        $this->sort($s, $m+1, $b);
    }
}

时间复杂度

经测试发现 第二种快排实现方式 是最快的,代码运行速度:①第二种快排实现方式 > ②归并排序 > ③第一种快排实现方式

递归调用的层数略小于 log₂n,每一层中总的循环次数是 n,所以时间复杂度为:O(nlog₂n)

最好情况(每次分割点刚好居中):O(nlog₂n)

最坏情况(每次分割点都居最左侧或者最右侧,这会导致递归层数与 n 接近):O(n²)

空间复杂度

每次递归到最底层时所花费的空间为 log₂n,因此空间复杂度为:O(log₂n)

本作品采用《CC 协议》,转载必须注明作者和本文链接
xiaer
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!