五、快速排序
原理
快速排序采用了和归并排序类似的分而治之的思想,归并排序中顺序的确定是在 治
中完成的,即在合并两个子数组时来确定顺序的。而快速排序是在 分
的时候就确定了顺序,合并两个子数组时只需顺序连接即可。
步骤
- 取原始数组下标 0 位置为分割点。
- 遍历原始数组,依据分割点将原始数组切分成 2 份,左边一份小于分割点, 右边另一份大于或等于分割点。
- 将左右数组传入递归函数继续分割,返回的数组按照
左数组 + 分割点 + 右数组
直接合并即可。
代码
第一种实现方式:新建左右临时数组,根据分割点分拣数据,最后将 左数组 + 分割点 + 右数组
合并。
<?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 协议》,转载必须注明作者和本文链接