PHP算法之四大基础算法

isLishude 发布于2019-07-01 12:31 / 2177人阅读

摘要：而在证明算法是正确的基础上，第二步就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。

前言

虽然工作中，你觉得自己并没有涉及到算法这方面的东西，但是算法是程序的核心，一个程序的好与差，关键是这个程序算法的优劣，所以对于冒泡排序、插入排序、选择排序、快速排序这四种基本算法，我想还是要掌握的。

冒泡排序法

冒泡排序大概的意思是依次比较相邻的两个数，然后根据大小做出排序，直至最后两位数。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

冒泡是从前往后冒，所以，每轮比较的次数也是逐渐减少的，最后一个数不用比较，其时间复杂度为O(n²)，算法如下：

/**
 * 冒泡排序算法
 * @param array $arr
 * @return array
 */
function bubble_sort($arr) {
    // 判断参数是否为数组，且不为空
    if (!is_array($arr) || empty($arr)) {
        return $arr;
    }
    // 循环需要冒泡的轮数
    for ($i = 1, $len = count($arr); $i < $len; $i++) {
        // 循环每轮需要比较的次数
        for ($j = 0; $j < $len - $i; $j++) {
            // 大的数，交换位置，往后挪
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j + 1];
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $temp;
            }
        }
    }
    return $arr;
}

选择排序法

选择排序的原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；以此类推，直到所有元素均排序完毕。

选择是每一次从假定一个最小值的位置，然后用假定最小值和后面的值依次比较，找到实际的最小值来放到假定最小值的位置上，其时间复杂度也为O(n²)，算法如下：

/**
 * 选择排序法
 * @param array $arr
 * @return array
 */
function select_sort($arr) {
    // 判断参数是否为数组，且不为空
    if (!is_array($arr) || empty($arr)) {
        return $arr;
    }
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        // 假设最小数的位置
        $min = $i;
        // 用假设的最小数和$i后面的数循环比较，找到实际的最小数
        for ($j = $i + 1; $j < $len; $j++) {
            // 后面的数比假设的最小数小，替换最小数
            if ($arr[$min] > $arr[$j]) {
                $min = $j;
            }
        }
        // 假设的最小数和实际不符，交换位置
        if ($min != $i) {
            $temp = $arr[$min];
            $arr[$min] = $arr[$i];
            $arr[$i] = $temp;
        }
    }
    return $arr;
}

插入排序法

插入排序的原理：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

插入排序法是先将排序元素的前两个元素排序，然后将第三个元素插入已经排序好的两个元素中，所以这三个元素仍然是从小到大排序，接着将第四个元素插入，重复操作直到所有元素都排序好；其时间复杂度同样为O(n²)，算法如下：

/**
 * 插入排序法
 * @param array $arr
 * @return array
 */
function insert_sort($arr) {
    // 判断参数是否为数组，且不为空
    if (!is_array($arr) || empty($arr)) {
        return $arr;
    }
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        // 当前需要比较的临时数
        $tmp = $arr[$i];
        // 循环比较临时数所在位置前面的数
        for ($j = $i - 1; $j >= 0; $j--) {
            // 前面的数比临时数大，则交换位置
            if ($arr[$j] > $tmp) {
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
    return $arr;
}

快速排序法

快速排序法是对冒泡排序的一种改进。他的基本原理是：通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行快速排序，整个排序过程可以递归进行，以达到整个序列有序的目的。

快速排序法是从数列中挑出第一个数（最后一个数）作为基准元素，然后循环所有数，和基准书比较分为左右两列，然后重复这样的步骤继续划分为左右两列，算法如下：

/**
 * 快速排序法
 * @param array $arr
 * @return array
 */
function quick_sort($arr) {
    // 判断参数是否为数组，且不为空
    if (!is_array($arr) || empty($arr)) {
        return $arr;
    }
    // 数组长度为1停止排序
    $len = count($arr);
    if ($len == 1) {
        return $arr;
    }
    // 声明左右两个空数组
    $left = $right = [];
    // 循环遍历，把第一个元素当做基准数
    for ($i = 1; $i < $len; $i++) {
        // 比较当前数的大小，并放入对应的左右数组
        if ($arr[$i] > $arr[0]) {
            $right[] = $arr[$i];
        } else {
            $left[] = $arr[$i];
        }
    }
    // 递归比较
    $left = quick_sort($left);
    $right = quick_sort($right);
    // 左右两列以及基准数合并
    return array_merge($left, [$arr[0]], $right);
}

使用方法

声明一个待排序的数组，然后调用对应的排序方法即可得到返回的排序好的数组；说明一下，我这里的排序设计都是递增的，如果需要递减，需要修改一下排序算法的比较替换符就行。

// 待排序数组
$arr = [1, 4, 5, 9, 3, 8, 6];
// 调用排序方法
$sort_arr = bubble_sort($arr);
// 输出打印
print_r($sort_arr);

分析算法

通常，对于一个给定的算法，我们要做两项分析：第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二步就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。还有我们通常说的：算法优化无非就是以时间换空间，以空间换时间，一般这两者是不可兼得。

结束语

实现一个程序，肯定是有多种算法的，大家有其他想说的，都可以留言和我交流，谢谢！如有问题，也欢迎指出，我会及时改正，谢谢！

服务器托管 idc机房托管 webrtc之vad算法看动画学算法之:hashtable 大数据算法基础图像识别算法基础

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

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

PHP面试总结

摘要：而在面试过程中，也是经常会遇到的，所以，无论是面试准备还是日常开发，我们都应该关注这方面的东西。二分法的基本做法是确定要查找的区间。区间内选取二分点。根据二分点的值，综合左右区间情况以及求解的目的，舍去一半无用的区间。 showImg(https://images.pexels.com/photos/935977/pexels-photo-935977.jpeg); 前言面试是你进入...

alin 2019-07-01 12:30 评论0 收藏0
一个老鸟发的公司内部整理的 Android 学习路线图

摘要：一个老鸟发的公司内部整理的学习路线图年月日阅读数发了一篇一个老鸟也发了一份他给公司内部小伙伴整理的路线图。另一份开发学习路线图。看完这本书后，小明对的历史结构代码规范等都有了一个大概的了解，并且，小明已经可以写出一些简单的了。一个老鸟发的公司内部整理的 Android 学习路线图 2017年09月12日 17:13:27 阅读数：20449 jixiaohua发了一篇一个老...

miya 2019-04-23 15:31 评论0 收藏0
机器视觉产业链全解析

摘要：在目前的整个机器视觉系统成本构成中，零部件及软件开发占据了的比例，是产业链中绝对的核心环节和价值获取者。光源的好坏在于对比度亮度和对位置变化的敏感程度，机器视觉行业主要采用光源产品。点击上方小白学视觉，选择加星标或置顶重磅干货，第一时间送达机器视觉（Machine Vision...

testbird 2021-09-22 10:02 评论0 收藏0
GIAC 2017全球互联网架构大会最新日程

摘要：月日至日，高可用架构和联合主办的全球互联网架构大会将于上海光大会展中心举行。全球互联网架构大会是高可用架构技术社区推广的面向架构师技术负责人及高端技术从业人员的技术架构大会。本次大会共有大板块方向，场技术专题，个互联网架构案例。 showImg(https://segmentfault.com/img/bVZ3Vh?w=600&h=375);12月22日至23日，高可用架构和msup联...

617035918 2019-06-26 18:17 评论0 收藏0
GIAC 2017全球互联网架构大会最新日程

摘要：月日至日，高可用架构和联合主办的全球互联网架构大会将于上海光大会展中心举行。全球互联网架构大会是高可用架构技术社区推广的面向架构师技术负责人及高端技术从业人员的技术架构大会。本次大会共有大板块方向，场技术专题，个互联网架构案例。 showImg(https://segmentfault.com/img/bVZ3Vh?w=600&h=375);12月22日至23日，高可用架构和msup联...

Imfan 2019-06-24 17:55 评论0 收藏0