PHP 算法 —— 快速排序

Apollo 发布于2019-07-01 12:38 / 2585人阅读

摘要：算法原理下列动图来自五分钟学算法，演示了快速排序算法的原理和步骤。因此，快速排序的遍历次数最少是次。为什么最多是次这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是。

算法原理

下列动图来自@五分钟学算法，演示了快速排序算法的原理和步骤。

步骤:

从数组中选个基准值

将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置

递归的对分列两边的数组再排序

代码实现

function quickSort($arr)
{
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }

    $v = $arr[0];
    $low = $up = array();
    for ($i = 1; $i < $len; ++$i) {
        if ($arr[$i] > $v) {
            $up[] = $arr[$i];
        } else {
            $low[] = $arr[$i];
        }
    }
    $low = quickSort($low);
    $up = quickSort($up);

    return array_merge($low, array($v), $up);
}

测试代码:

$startTime = microtime(1);

$arr = range(1, 10);
shuffle($arr);

echo "before sort: ", implode(", ", $arr), "
";
$sortArr = quickSort($arr);
echo "after sort: ", implode(", ", $sortArr), "
";

echo "use time: ", microtime(1) - $startTime, "s
";

测试结果:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8
after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
use time: 0.0009009838104248s

时间复杂度

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。

这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。

1) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。

2) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

参考资料

快速排序

十大经典排序算法动画与解析

感谢您的阅读，觉得内容不错，点个赞吧

云服务器 GPU云服务器快速排序算法最好的快速排序算法最快速的排序算法 php快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31141.html

php 经典排序算法（解析）

摘要：介绍三种排序算法快速排序选择排序冒泡排序选择排序选择排序是一种简单直观的排序算法。介绍三种排序算法快速排序选择排序冒泡排序选择排序选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3...

FuisonDesign 2019-06-28 14:08 评论0 收藏0
PHP 快速排序算法

摘要：概念这里借用百度百科的一张图来，非常形象快速排序算法是对冒泡算法的一个优化。获取已经打乱了顺序的数组快速排序这里引用的是我之前写的冒泡算法排序冒泡运行结果概念这里借用百度百科的一张图来，非常形象：showImg(https://segmentfault.com/img/bVdlR6); 快速排序算法是对冒泡算法的一个优化。他的思想是先对数组进行分割，把大的元素数值放到一个临时数...

Coly 2019-06-27 10:56 评论0 收藏0
快速排序算法图解与PHP实现讲解

摘要：概述快速排序最初由东尼霍尔提出，是一种平均时间复杂度为，最差时间复杂度为的排序算法。测试算法效率与复杂度完全随机序列排序结果以下面的方法分别生成元素个数为万万的完全随机数组，并用快速排序算法对其排序。概述快速排序（QuickSort）最初由东尼·霍尔提出，是一种平均时间复杂度为showImg(https://segmentfault.com/img/bV5sdO?w=61&h=17...

shleyZ 2019-06-28 18:31 评论0 收藏0
PHP算法之四大基础算法

摘要：而在证明算法是正确的基础上，第二步就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言虽然工作中，你觉得自己并没有涉及到算法这方面的东西，但是算法是程序的...

isLishude 2019-07-01 12:31 评论0 收藏0
PHP面试：尽可能多的说出你知道的排序算法

摘要：良好的排序算法具有进行最少的比较和交换的特征。冒泡排序是一个基于比较的排序算法，被认为是效率最低的排序算法之一。现在让我们使用实现冒泡排序算法。插入排序到目前为止，我们已经看到了两种基于比较的排序算法。预警本文适合对于排序算法不太了解的新手同学观看，大佬直接忽略即可。因为考虑到连贯性，所以篇幅较长。老铁们看完需要大概一个小时，但是从入门到完全理解可能需要10个小时(哈哈哈，以我自己...

objc94 2019-07-01 10:39 评论0 收藏0