资讯专栏INFORMATION COLUMN

php 经典排序算法(解析)

FuisonDesign / 2170人阅读

摘要:介绍三种排序算法快速排序选择排序冒泡排序选择排序选择排序是一种简单直观的排序算法。

介绍三种排序算法

快速排序

选择排序

冒泡排序

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。

简单解释
首先默认序列的第一个元素为最小值A,然后从剩下的序列里面,选取最小值B,如果B

code

function selectSort($arr) {
    $len = count($arr);

    for($i = 0 ; $i < $len - 1; $i ++) {
        // 默认第一个是最小值
        $min = $i;
        // 注意这里是从$i + 1 开始遍历剩余的元素,选出最小值
        for($n = $i + 1 ; $n < $len; $n ++) {
            if($arr[$n] < $arr[$min]) {
                $min = $n;
            }
        }
        // 如果最小值不是当前默认的最小值,那么进行替换
        if($min != $i) {
            $t = $arr[$i];
            $arr[$i] = $arr[$min];
            $arr[$min] = $t;
        }
    }

    return $arr;
}
冒泡排序

比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

简单解释
要比较N轮,每轮都要比较N-当前轮次的次数, 每次都会选出一个最大值放到后面(有点抽象)

代码

function bubbleSort($arr) {
    $len = count($arr);
    // 这里比较N次
    for($i = 0; $i< $len - 1; $i++) {
        // 每次比较实际上都要-$i,因为每次比较结束后最后一个值就不用参与下次比较了
        for($n = 0; $n < $len - 1 - $i; $n ++) {
            if($arr[$n] > $arr[$n + 1]) {
                $t = $arr[$n];
                $arr[$n] = $arr[$n + 1];
                $arr[$n + 1] = $t;
            }
        }
    }

    return $arr;

}
快速排序(真的很快)

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

简单解释
这个真的更抽象,因为,就是将小的放一边,大的放一边,然后递归出来

code

function quickSort($arr) {
    $len = count($arr);
    // 因为是递归,所以如果最后的数组可能是空的也可能是1个,那么就没有可比较的了,直接返回
    if($len <= 1) {
        return $arr;
    }

    $base = $min = $max = [];

    $base_item = $arr[0];

    for($i = 0; $i < $len ; $i++) {
        if($arr[$i] < $base_item) {
            $min[] = $arr[$i];
        }elseif($arr[$i] > $base_item) {
            $max[] = $arr[$i];
        }else {
            $base[] = $arr[$i];
        }
    }

    $min = quickSort($min);
    $max = quickSort($max);
    // 每次构造新的序列
    return array_merge($min,$base,$max);
}
性能测试

这三个排序算法的时间复杂度是不一样的,我们来测试下性能。我们用下面代码来生成散列数组。

$arr = range(0,$argv[1]);
shuffle($arr);

然后执行上面三个方法

$time = execTime();
// 快速排序
quickSort($arr);
$time = execTime($time);
// 选择排序
selectSort($arr);
$time = execTime($time);
// 冒泡排序
bubbleSort($arr);
$time = execTime($time);

// 这个是计算毫秒耗时的方法
function execTime($microTime = 0) {
    $microTime && var_dump(microtime(true)*1000 - $microTime);
    return microtime(true)*1000;
}

看下执行结果,果然最快的是快速排序

php sort_practice.php  10
float(0.0419921875)
float(0.011962890625)
float(0.011962890625)

php sort_practice.php  100
float(0.30908203125)
float(0.396240234375)
float(0.779052734375)

php sort_practice.php  200
float(0.687744140625)
float(1.93994140625)
float(3.37890625)

php sort_practice.php  300
float(0.85400390625)
float(3.222900390625)
float(8.123046875)

php sort_practice.php  400
float(1.23193359375)
float(5.857177734375)
float(11.824951171875)

php sort_practice.php  500
float(1.559814453125)
float(8.73291015625)
float(21.15087890625)

php sort_practice.php  600
float(1.70703125)
float(14.300048828125)
float(30.343994140625)

php sort_practice.php  700
float(2.265869140625)
float(18.0390625)
float(41.654052734375)

php sort_practice.php  800
float(2.581298828125)
float(24.72998046875)
float(53.56005859375)

php sort_practice.php  900
float(2.682861328125)
float(31.9560546875)
float(65.988037109375)

php sort_practice.php  1000
float(3.18701171875)
float(36.010986328125)
float(78.216064453125)

php sort_practice.php  2000
float(6.450927734375)
float(151.62475585938)
float(313.64624023438)

php sort_practice.php  3000
float(11.026123046875)
float(362.6640625)
float(721.11572265625)

php sort_practice.php  4000
float(15.346923828125)
float(667.11791992188)
float(1314.2221679688)

php sort_practice.php  5000
float(20.559814453125)
float(1029.8937988281)
float(2057.3466796875)

php sort_practice.php  6000
float(27.767822265625)
float(1534.2431640625)
float(2917.7407226562)

php sort_practice.php  7000
float(33.481201171875)
float(2083.5861816406)
float(3984.7060546875)

php sort_practice.php  8000
float(38.852783203125)
float(2606.0270996094)
float(5157.6708984375)

php sort_practice.php  9000
float(42.02587890625)
float(3436.4509277344)
float(6638.451171875)

php sort_practice.php  10000
float(45.932861328125)
float(4640.3000488281)
float(8474.2751464844)
二分搜索查找

再写一个经典搜索

先从中间开始找,递归类似快速排序

$arr = range(0, $argv[1]);
$value = mt_rand(0, count($arr));

var_dump($value);

function binSearch($value, $arr) {
    if(!$arr) {
        return false;
    }
    $sign = floor(count($arr)/2);
    $middle = $arr[$sign];

    if($middle == $value) {
        var_dump($middle);
    }else {
        binSearch($value,array_slice($arr, 0, $sign));
        binSearch($value,array_slice($arr, $sign + 1));
    }
}


binSearch($value,$arr);

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

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

相关文章

  • PHP 算法 —— 快速排序

    摘要:算法原理下列动图来自五分钟学算法,演示了快速排序算法的原理和步骤。因此,快速排序的遍历次数最少是次。为什么最多是次这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是。 算法原理 下列动图来自@五分钟学算法,演示了快速排序算法的原理和步骤。 showImg(https://shockerli.net/media/15540242976690/quick.gif); 步骤: ...

    Apollo 评论0 收藏0
  • PHP基础

    摘要:分别为适配器模式,装饰器模式,代理模式,外观模式,桥接模式,组合模式,享元模式。设计模式五适配器模式适配器模式将某个对象的接生成器和协程的实现在这篇文章中,作者针对那些比较难以理解的概念,以一个更为通俗的方式去讲明白。。 PHP 源码注解 PHP 的详细源码注解 PHP 字符串操作整理 一些有关字符串的常用操作。 Redis 常见七种使用场景 (PHP 实战) 这篇文章主要介绍利用 R...

    HtmlCssJs 评论0 收藏0
  • PHP实现几种经典算法详解

    摘要:冒泡排序数组排序快速排序数组排序二分查找数组里查找某个元素顺序查找数组里查找某个元素线性表的删除数组中实现附其详细场景题目经典算法实现案例 1、冒泡排序(数组排序) function bubble_sort( $array) { $count = count( $array); if ($count

    aikin 评论0 收藏0
  • PHPer 面试指南-扩展阅读资源整理

    摘要:前端篇收集的前端面试题和答案前端开发面试题史上最全的前端面试题汇总及答案前端工程师手册协议工作原理协议运行机制的概述协议篇原理原理解析的工作原理与的区别理解后端篇年的面试总结垃圾回收机制面向对象设计浅谈说清楚是什么和的区别索引原理及慢查 前端篇 收集的前端面试题和答案 前端开发面试题 史上最全的web前端面试题汇总及答案 前端工程师手册 HTTP协议:工作原理 SSL/TLS协议运行...

    wemall 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<