博主信息
智仙生
博文
2
粉丝
0
评论
2
访问量
450
积分:0
P豆:6.5
最新更新
PHP开源项目网址大全2021-07-20
PHP算法2021-06-30
博文分类
算法1篇
PHP1篇
MySQL0篇
Linux0篇
ThinkPHP0篇
Laravel0篇
Yii0篇
前端0篇

PHP算法

2021年06月30日 10:54:08阅读数:399博客 / 智仙生/ 算法

1.冒泡排序

        冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,依次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    步骤:

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

    代码:

                 //冒泡排序

                $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
                 $len = count($arr);
                  //该层循环控制 需要冒泡的轮数
                  for ($i = 0; $i <= $len; $i++) {
                        //该层循环用来控制每轮 冒出一个数 需要比较的次数
                         for ($k = 0; $k < $len - $i; $k++) {
                                if ($arr[$k] > $arr[$k + 1]) {    //从小到大 >   从大到小 <
                                     $tmp = $arr[$k + 1]; // 声明一个临时变量
                                     $arr[$k + 1] = $arr[$k];
                                     $arr[$k] = $tmp;
                                 }
                          }
                   }

            print_r($arr);

    排序效果:

                 599210-20170619085503132-2067568088.gif

2.选择排序

        选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

    代码:

                $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];//选择排序
                //实现思路 双重循环完成,外层控制轮数,当前的最小值。内层控制比较次数

                 $len = count($arr);    //$i 当前最小值的位置, 需要参与比较的元素

                  for ($i = 0; $i < $len - 1; $i++) {        //先假设最小的值的位置
                      $p = $i;        //$j 当前都需要和哪些元素比较,$i 后边的。
                      for ($j = $i + 1; $j < $len; $j++) {            //$arr[$p] 是 当前已知的最小值
                          //比较,发现更小的,记录下最小值的位置;并且在下次比较时,应该采用已知的最小值进行比较。
                          $p = ($arr[$p] <= $arr[$j]) ? $p : $j;
                       }        //已经确定了当前的最小值的位置,保存到$p中。
                       //如果发现 最小值的位置与当前假设的位置$i不同,则位置互换即可
                       if ($p != $i) {            

                            $tmp     = $arr[$p];            

                            $arr[$p] = $arr[$i];            

                            $arr[$i] = $tmp;
                       }
                   }    //返回最终结果
                  print_r($arr);

     排序效果:

            1094457-20170313214825557-329405797.gif

3.插入排序

        插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

    步骤:

        从第一个元素开始,该元素可以认为已经被排序取出下一个元素,在已经排序的元素序列中从后向前扫描如果该元素(已排序)大于新元素,将该元素移到下一位置重复步骤3,直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置中重复步骤2

    代码:

            $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
            //插入排序
            $len=count($arr);
            for($i=1; $i<$len; $i++) {
                 //获得当前需要比较的元素值
                 $tmp = $arr[$i];
                 //内层循环控制 比较 并 插入
                 for($j=$i-1; $j>=0; $j--) {
                      //$arr[$i];需要插入的元素
                      //$arr[$j];需要比较的元素
                      if($tmp < $arr[$j])   //从小到大 < || 从大到小 >
                      {
                           //发现插入的元素要小,交换位置
                           //将后边的元素与前面的元素互换
                           $arr[$j+1] = $arr[$j];
                          //将前面的数设置为 当前需要交换的数
                          $arr[$j] = $tmp;
                      } else {
                          //如果碰到不需要移动的元素
                          //由于是已经排序好是数组,则前面的就不需要再次比较了。
                          break;
                      }
                 }
           }
           print_r($arr);

    排序效果:

 insert-sort.gif

4.快速排序

        快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

    步骤:

        从数列中挑出一个元素,称为 “基准”(pivot),重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    代码:

            $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];

            //快速排序

            function quick_sort($arr){   

                     //判断参数是否是一个数组    

                     if(!is_array($arr)) return false;    

                     //递归出口:数组长度为1,直接返回数组   

                     $length = count($arr);   

                      if($length<=1) return $arr;    

                    //数组元素有多个,则定义两个空数组   

                     $left = $right = array();    

                    //使用for循环进行遍历,把第一个元素当做比较的对象   

                     for($i=1; $i<$length; $i++)   

                     {        

                            //判断当前元素的大小       

                             if($arr[$i] < $arr[0]){  //从小到大 < || 从大到小 >            

                                $left[]=$arr[$i];        

                              }else{            

                                $right[]=$arr[$i];       

                             }   

                      }   

                     //递归调用    

                    $left=quick_sort($left);   

                     $right=quick_sort($right);    

                    //将所有的结果合并    

                    return array_merge($left,array($arr[0]),$right);

            }

            $arr = quick_sort($arr);

            print_r($arr);

    排序效果:

        1070689-20170519001857025-173745062.gif

4.归并排序

        利用递归,先拆分、后合并、再排序。

    步骤:

        均分数列为两个子数列递归重复上一步骤,直到子数列只有一个元素父数列合并两个子数列并排序,递归返回数列

    代码:

        $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];

        // 归并排序主程序
        function mergeSort($arr) {
               $len = count($arr);
               // 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组
               if ($len <= 1) {
                       return $arr;
               }

             $mid  = intval($len / 2);             // 取数组中间
             $left = array_slice($arr, 0, $mid); // 拆分数组0-mid这部分给左边left
             $right= array_slice($arr, $mid);          // 拆分数组mid-末尾这部分给右边right
             $left = mergeSort($left);                 // 左边拆分完后开始递归合并往上走
             $right= mergeSort($right);                // 右边拆分完毕开始递归往上走
             $arr  = merge($left, $right);             // 合并两个数组,继续递归

             return $arr;
        }

        // merge函数将指定的两个有序数组(arrA, arr)合并并且排序
        function merge($arrA, $arrB) {
                   $arrC = array();
                   while (count($arrA) && count($arrB)) {
                           // 这里不断的判断哪个值小, 就将小的值给到arrC, 但是到最后肯定要剩下几个值,
                           // 不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值, 肯定比arrC里面所有的值都大所以使用
                           //从小到大 < || 从大到小 >
                           $arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);
                   }
                   return array_merge($arrC, $arrA, $arrB);
        }

        $arr = mergeSort($arr);
        print_r($arr);

排序效果:

 merge.gif


版权申明:本博文版权归博主所有,转载请注明地址!如有侵权、违法,请联系admin@php.cn举报处理!

全部评论

文明上网理性发言,请遵守新闻评论服务协议

条评论
BUG攻城狮
  • BUG攻城狮· 2021-07-01 08:24:161楼
  • 后续会有平时项目接触的一些知识分享,敬请期待!

  • 回复
  • 在前面的文章中,我们给大家介绍了三种递归的实现方,即“静态变量”、“全局变量”、“引用传参”。需要的朋友可以了解《PHP递归(一)》《PHP递归(二)》《PHP递归(三)》
    在《PHP递归(一)》和《PHP递归(二)》中,我们分别为大家介绍了如何用静态变量和全局变量的方式实现递归。本篇文章我们继续为大家讲解如何通过引用传参的方式来实现。
    在前面的文章《PHP随机取一(一)》中,我们为大家简单介绍了PHP取一的面试问题。下面我们继续结合之前的内容,给大家详细讲解PHP取一
    在前面的文章《PHP递归(一)》中,我们为大家介绍了如何利用静态变量的方来实现递归。本篇文章我们就继续为大家介绍另一种实现递归的方即通过全局变量。
    在前面的文章《PHP随机取一(二)》中,我们详细的为大家介绍PHP随机取一的实现思路,也就是“公平选猴王”面试题的解决方
    php中计整数除,利用整数除函数 intdiv()
    下面由php教程栏目带大家介绍关于php国密SM3签名,希望对需要的朋友有所帮助!
    本篇文章给大家简析PHP拆红包,有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。
    本次我们将讨论 PHP 中逻辑运符的应用。逻辑运符 (1) &&(and) 逻辑与 (2) ||(or) 逻辑或 (3) !(not) 逻辑非,一元运符。
    php中查找有很多种,你知道的有哪几种呢?对于查找的含义你又是如何理解的?本篇文章就是带你去探索关于的一些奥秘,一起探讨数组中什么是查找?如何查找?
    php实现排序的方:1、冒泡排序,两两相比,每循环一轮就不用再比较最后一个元素;2、选择排序,选定一个作为基本值,剩下的和这个比较,再调换位置。
    php实现md5:1、当数组元素超过整形长度时的自动转换;2、实现无符号右移操作;3、将字符串转换成8位存储为一个元素的数据结构。
    PHP如何使用位运实现四则运?本篇文章给大家介绍一下在PHP中使用位运实现四则运(加减乘除运)的方
    php几天前的方:首先创建一个PHP示例文件;然后通过“function time_tran($time){...}”方几天前的时间即可。
    ​本篇文章向大家介绍整理常见的PHP面试题,有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。
    本篇文章给大家介绍一下实现php数组冒泡排序的方,以简单实例形式分析了php数组冒泡排序的实现原理与相关技巧。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。
    程序员对哈希应该都不陌生,比如业界著名的MD5、SHA、CRC等等,在日常开发中我们经常用一个Map来装载一些具有(key,value)结构的数据,利用哈希O(1)的时间复杂度提高程序处理效率。
    下面是整理好的几道php面试题,在近几年中这些题目频繁出现在面试题中,现在分享给大家,希望能对大家有所帮助。
    php实现计剩余几天的方:首先创建一个PHP示例文件;然后通过“function ShengYu_Tian_Shi_Fen($unixEndTime=0){...}”方实现计剩余几天即可。
    的五个特性是:1、有穷性,必须能在执行有限个步骤之后终止;2、确切性,的每一步骤必须有确切的定义;3、输入项,一个有0个或多个输入;4、输出项,一个有一个或多个输出;5、可行性