文档章节

php之常用算法实现

baihan
 baihan
发布于 2013/10/14 02:34
字数 1993
阅读 79
收藏 1
点赞 0
评论 0
<?php
$arr = array(35,66,2,15,6,81,6,9,0,-2,9); 
    /* 堆排序: 利用大(小)顶堆的特性,不断调整堆,依次选出待排序列中最大、次大值。 
    代码参考自:http://www.cnblogs.com/zemliu/archive/2012/08/18/2645941.html 
    */ 
     function heapSort(&$arr) { 
         #初始化大顶堆 为什么要初始化,其实是为了找出待排序列中最大的值 
         initHeap($arr, 0, count($arr) - 1); 
         //print_r($arr);exit; 
         #开始交换首尾节点,并每次减少一个末尾节点再调整堆,直到剩下一个元素 
         for($end = count($arr) - 1; $end > 0; $end--) {  // 依次取出大顶堆中第一个根节点即最大值,并重新调整,即 
         //依次选出次大的元素 
             $temp = $arr[0]; 
             $arr[0] = $arr[$end]; 
             $arr[$end] = $temp; 
             ajustNodes($arr, 0, $end - 1); 
         } 
     } 
      
     #初始化最大堆,从最后一个非叶子节点开始,最后一个非叶子节点编号为 数组长度/2 向下取整 
     function initHeap(&$arr) { 
         $len = count($arr); 
         for($start = floor($len / 2) - 1; $start >= 0; $start--) { 
             ajustNodes($arr, $start, $len - 1); 
         } 
     } 
      
     #调整节点 
     #@param $arr    待调整数组 
     #@param $start    调整的父节点坐标 
     #@param $end    待调整数组结束节点坐标 
     function ajustNodes(&$arr, $start, $end) { 
         $maxInx = $start; // 根节点 
         $len = $end + 1;    #待调整部分长度 
         $leftChildInx = ($start + 1) * 2 - 1;    #左孩子坐标 
         $rightChildInx = ($start + 1) * 2;    #右孩子坐标 
          
         #如果待调整部分有左孩子,调换左孩子与根节点,看哪个作为根节点 
         if($leftChildInx + 1 <= $len) { 
             #获取最小节点坐标 
             if($arr[$maxInx] < $arr[$leftChildInx]) { 
                 $maxInx = $leftChildInx; 
             } 
         } 
         #如果待调整部分有右子节点 , 接上面的调整, 继续调换右孩子与根节点,看哪个作为根节点 
         if($rightChildInx + 1 <= $len) { 
             if($arr[$maxInx] < $arr[$rightChildInx]) { 
                 $maxInx = $rightChildInx; 
             } 
         } 
         // 上面调整结束后,根、左、右三个节点中,根节点一定是最大值 即maxInx是最大值的索引。 
         #交换父节点和最大节点 
         if($start != $maxInx) { 
             // 将最大值的节点调整为根节点 
             $temp = $arr[$start]; 
             $arr[$start] = $arr[$maxInx]; 
             $arr[$maxInx] = $temp; 
              
             #如果交换后的子节点还有子节点,继续调整 
             if(($maxInx + 1) * 2 <= $len) {// 依次反复 
                 ajustNodes($arr, $maxInx, $end); 
             } 
         } 
     } 
      
     $arr = array(35,66,2,15,6,81,6,9); 
     heapSort($arr); 
     print_r($arr); 
/* 
计数排序:依次计算出待排序列中每个元素比他大(小)的元素个数。然后根据这个个数依次输出即可 
得出有序的序列。缺点是:需要的空间巨大,特别是待排序列元素个数小,但是最大值却巨大的情况下, 
性能极差。 
*/ 
function count_sort($ary) { 
    $tmp = array(); 
    for($i = 0;$i< count($ary);$i++) { //第一步,需要找出最大值 
        if($max < $ary[$i]) { 
            $max = $ary[$i]; 
        } 
    } 
    for($i = 0;$i < $max;$i++) { 
        $tmp[$i] = 0; 
    } 
    for($i = 0;$i < count($ary);$i++) { 
        $tmp[$ary[$i]]++; 
    } 
     
    for ($i = 1; $i < count($tmp); $i++) { 
        $tmp[$i] += $tmp[$i-1]; 
    } 
    //print_r($tmp); 
    for ($i = 0; $i < count($ary); $i++) { 
        $tmp_ary[$tmp[$ary[$i]]] = $ary[$i]; 
        $tmp[$ary[$i]]--; 
    } 
     
    for ($i = 0; $i < count($tmp_ary); $i++) { 
        $ret[] = $tmp_ary[$i]; 
    } 
    return $ret; 
} 
$arr = array(35,66,2,15,6,81,6,44); 
print_r(count_sort($arr)); 

/* 
快速排序:经过一趟遍历,根据某一基数[一般是第一个元素]将待排序列调整为大值在右边, 
小值在左边的一个序列。按照这种方式不断递归的调整直到待排序列只剩下一个元素。 
利用分治的思想,将待排序列每次分为左边小、右边大的两个序列,并依次对各子序列进行排序。
和归并排序异同:都使用的分治的思想,先分后合。但是,快速排序经排序的过程集中在分的过程中了,
而归并排序则是将排序的过程集中在合的过程中。
*/ 
function quick_sort($ary) { 
    if(count($ary) > 1) { 
        $left = array(); 
        $right = array(); 
        $pivot = $ary[0]; 
        for($i = 1;$i< count($ary);$i++) { 
            if($ary[$i] >= $pivot) $right[] = $ary[$i]; 
            else $left[] = $ary[$i]; 
        } 
         
        $left = quick_sort($left); 
        $right = quick_sort($right); 
        return array_merge($left,array($pivot),$right); 
    } else { 
        return $ary; 
    } 
} 
$arr = array(35,66,2,15,6,81,6,9); 
$sort_ary = quick_sort($ary); 
print_r($sort_ary); 
/* 
快速排序第二个版本。*/ 
function partition(&$ary,$low,$high) { 
    $tmp = $ary[$low]; 
    while($low < $high) { 
        while($low < $high && $ary[$high] >= $tmp) {  
            $high--; 
        } 
        $ary[$low] = $ary[$high];// 巧妙之处: 这里只要一发生交换,下面的low就必须往前走一步
        while($low < $high && $ary[$low] <= $tmp) { 
            $low++; 
        } 
        $ary[$high] = $ary[$low];// 这里只要一发生交换,上面的high就必须往前走一步,这样一来,其实左右 
        // 调换过来的元素并没有相互覆盖掉。 
    } 
    $ary[$low] = $tmp;// 最后,需要把基数赋值给low下标,此时的low下面就是调整后次序列的分水岭,右边值大,左边值小 
    return $low; 
} 


function quick_sort2(&$ary,$low,$high) { 
    if($low < $high) { 
        $p = partition($ary,$low,$high); 
        quick_sort($ary,$low,$p - 1); 
        quick_sort($ary,$p+1,$high); 
    } 
    return $ary; 
} 
$arr = array(35,66,2,15,6,81,6,9); 
$sort_ary = quick_sort2($ary,0,count($ary)); 
print_r($sort_ary); 

/* 
/* 直接插入排序*/ 
function cr_sort1($ary) { 
    for($i = 1;$i < count($ary);$i++) { 
        $tmp = $ary[$i]; 
        $j = $i - 1;     
        while($j>=0 && $ary[$j] > $tmp) { 
            $ary[$j + 1] = $ary[$j]; 
            $j--; 
        } 
        $ary[$j+1] = $tmp; 
    } 
    return $ary; 
} 

// 插入排序另一种写法 
function cr_sort2($ary) { 
    for($i=1;$i < count($ary);$i++) { 
        $tmp = $ary[$i]; 
        $j = $i; 
        while($j >= 0 && $tmp < $ary[$j-1]) { 
            $ary[$j] = $ary[$j-1];// 往后移 
            $j--; 
        } 
        $ary[$j] = $tmp;// 插入 
    } 
    return $ary; 
} 
/*折半插入:由于普通的插入算法是依次将待排序的元素与已经完成排序的序列每一个元素做比较, 
然后插入到合适位置。二分插入的出现是为了减少元素的比较次数,本质是对插入排序的优化。 
具体思想是:利用二分查找,直接将待排序的那个元素定位到有序序列中需要插入的位置。这是优化的关键点。 
*/ 
function cr_sort3($ary) { 
    for($i = 1;$i < count($ary);$i++) { 
        $tmp = $ary[$i]; 
        $j = $i - 1; 
        $low = 0; 
        $high = $i - 1; 
        while($low <= $high) { 
            $mid = floor(($low + $high) / 2); 
            if($tmp > $ary[$mid]) $low = $mid + 1; 
            else  $high = $mid - 1; 
        } 
         
        while($j >= $low) { 
            $ary[$j + 1] = $ary[$j]; 
            $j--; 
        } 
        $ary[$low] = $tmp; 
    } 
    return $ary; 
} 
/* 
希尔排序:对插入排序的改进版。 基本算法是建立在直接插入排序算法之上的。 
基本思想是:按照某递增量,“间隔”的将待排序列调整为有序的序列。跳跃性的插入排序。 

*/ 
function shell_sort($ary) { 
    $d = count($ary); 
    while($d  > 1) { 
        $d  = intval($d / 2); //递增 
        for($i = $d;$i < count($ary);$i+=$d) { 
            $tmp = $ary[$i]; 
            $j = $i - $d;     
            while($j >= 0 && $ary[$j] > $tmp) { 
                $ary[$j + $d] = $ary[$j]; 
                $j -= $d; 
            } 
            $ary[$j+$d] = $tmp; 
        } 
    } 
    return $ary; 
} 

// 选择排序: 每次从待排序列中选出最大、次大的元素 
function xz_sort(&$ary) { 
    for($i = 0;$i < count($ary);$i++) { 
        $tmp = $ary[$i]; 
        for($j = $i+1;$j < count($ary);$j++) { 
            if($ary[$i] > $ary[$j]) { 
                $sit = $j; 
                $ary[$i] = $ary[$j]; 
            } 
        } 
        if($tmp != $ary[$i]) { 
            $ary[$sit] = $tmp; 
        } 
        //$ary[$i] = $flag; 
    } 
    return $ary; 
} 




$ary = array(23,-2,9,0,89,100,-23); 
$ary = cr_sort1($ary); 
print_r($ary); 
// 冒泡: 依次比较相邻的元素,两两比较,就可以最终将最大(小)的元素调整到最顶端、次顶端、、、 
// 下面的两种写法: 一是从前向后冒泡,第一次将对打元素冒到最上面、第二次冒到次下面。 
// 第二种:从后向前冒泡。 

function mp_sort2(&$ary) { 
    for($i = 0;$i < count($ary);$i++) { 
        for($j = 0;$j < count($ary) - $i - 1;$j++) { 
            if($ary[$j] > $ary[$j+1]) { 
                $tmp = $ary[$j]; 
                $ary[$j] = $ary[$j+1]; 
                $ary[$j+1] = $tmp; 
            } 
             
        } 
    } 
    return $ary; 
} 

function mp_sort(&$ary) { 
    for($i = 0;$i < count($ary);$i++) { 
        for($j = count($ary)-2;$j >= $i;$j--) { 
            if($ary[$j] > $ary[$j+1]) { 
                $tmp = $ary[$j]; 
                $ary[$j] = $ary[$j+1]; 
                $ary[$j+1] = $tmp; 
            } 
        } 
    } 
    return $ary; 
} 

// 二分查找 非递归算法 
function div_search($ary,$key) { 
    $low = 0; 
    $high = count($ary) - 1; 
    $i = 0; 
    while($low <= $high) { 
        $mid = floor(($high+$low)/2); 
        if($key == $ary[$mid]) return $key; 
        elseif($key < $ary[$mid]) $high = $mid -1;// 唯有这样,范围才会不断缩小啊 
        else $low = $mid + 1; 
    } 
} 
// 二分查找 递归算法 
function re_div_search($ary,$key,$low,$high) { 
    $mid = floor(($high+$low)/2); 
    if($key == $ary[$mid]) return $key; 
    elseif($key < $ary[$mid]) return re_div_search($ary,$key,$low,$mid -1); 
    else return re_div_search($ary,$key,$mid + 1,$high); 
} 
// 回溯法找子串 
function find_str($str,$substr) { 
    $i = 0; 
    $j =0 ; 
    while($i<strlen($str) && $j<strlen($substr)) { 
        if($str[$i]==$substr[$j]) { 
            $i++; 
            $j++; 
        } else { 
            $i = $i - $j +1; // 不相等的情况下,i是要向前走的哦! 
            $j = 0; 
        } 
    } 
    if($j == strlen($substr)) return true; 
    return false; 
} 

$str = 'XXXhello world'; 
$substr = 'ld'; 
echo find_str($str,$substr); 
exit; 

// 斐波那契数列 
function findN($n) { 
    if($n <= 2) return 1; 
    return findN($n-2)+findN($n-1); 
} 
// 斐波那契数列的非递归形式 
function findN1($n) { 
    $arr = array(1,1); 
    if($arr <= 2) return $arr; 
    for($i = 2;$i < $n;$i++) { 
        $arr[] = $arr[$i-1] + $arr[$i-2] ; 
    } 
    return implode(',',$arr); 
} 
print_r(findN1(7));exit; 
for($i = 1;$i<=20;$i++) { 
    echo findN($i); 
    echo '<br>'; 
} 
exit; 


//$ary = array(100,1,10,10,2,8,890,4,-98,39,89,12,-2); 

//$ary = mp_sort($ary); 

//print_r($ary);

本文转载自:

共有 人打赏支持
baihan
粉丝 1
博文 12
码字总数 2584
作品 0
深圳
高级程序员
php&go&python&node

2016 第二届 PHP 全球开发者大会回顾(文末附演讲嘉宾所有资料下载) 继前年的 “PHP7 初探”、去年的“高性能的 PHP ” 主题后,2017 第三届 PHP 全球开发者大会的活动主题是“高可用的 PH...

掘金官方
2017/12/20
0
0
浅谈 PHP 中的多种加密技术及代码示例

同样是一道面试答错的问,面试官问我非对称加密算法中有哪些经典的算法? 当时我愣了一下,因为我把非对称加密与单项散列加密的概念弄混淆了,所以更不用说什么非对称加密算法中有什么经典算...

snowing1990
2016/04/13
28
0
送给和我一样曾经浮躁过的PHP程序猿

送给和我一样曾经浮躁过的PHP程序猿 2012年偶决定开始写博客了,不为别的,就希望可以通过博客记录我的成长历程,同时也希望可以帮助一些刚毕业,刚入行业的兄弟姐们 们。我们是一群充满浮躁...

thinkyoung
2015/09/07
0
0
除了switch,PHP就不能像Python一样使用Map来代替多分枝条件语句吗? (只讨论技术)

不可否认,语言之争经常是活跃网络气氛的一把好手!今天看到一个,感觉有点意思,同时也引发了我的进一步思考。有同学说Python么有Switch语法,Python这点不爽云云,又有同学说Python有MAP,...

NILYANG
2016/07/08
40
0
排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien
2016/06/17
41
0
PHP常用的非对称加密

加密算法的分类 1)不可逆加密算法 2)可逆加密算法 可逆加密算法又分为两大类:“对称式”和“非对称式”。 openssl 实现RSA非对称加密 class Rsa{ //私匙 private $privKey = '-----BEGIN...

xinson
2016/04/20
401
0
共青团中央网络影视中心招聘PHP

岗位职责: -配合系统分析人员完成软件系统以及模块的需求分析和了解; -负责系统的功能定义,程序设计; -负责有关技术方案、文档的编写; -保证编码质量,不定期做代码检查并做BUG分析; ...

guhongzi
2014/09/24
0
0
memcached精讲第二部

老男孩之memcached精讲第二部 1.1Memcache 服务器的安装。 Linux,FreeBSD,Solaris,windows。这里以Centos6.4为例进行说明。 软件地址:Memcached 下载地址: libevent 下载地址: 网友安装...

妙曼
2017/02/20
0
0
PHP 之模板模式

我们可能会遇到这种情况,为了实现一些业务逻辑,我们会对同一个对象来回重建进行业务处理 比如说做试卷,老师除了一套试卷,学生们拿到试卷只有两个地方不一样,填写的答案和名字 这样的话,...

jackdongting
2017/08/09
0
0
一致性哈希算法以及其PHP实现

在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(...

晨曦之光
2012/03/09
609
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

前端基础

1. get请求传参长度的误区 误区:我们经常说get请求参数的大小存在限制,而post请求的参数大小是无限制的。 实际上HTTP 协议从未规定 GET/POST 的请求长度限制是多少。对get请求参数的限制是...

wenxingjun
29分钟前
0
0
Android 复制和粘贴功能

做了一回搬运工,原文地址:https://blog.csdn.net/kennethyo/article/details/76602765 Android 复制和粘贴功能,需要调用系统服务ClipboardManager来实现。 ClipboardManager mClipboardM...

她叫我小渝
今天
0
0
拦截SQLSERVER的SSL加密通道替换传输过程中的用户名密码实现运维审计(一)

工作准备 •一台SQLSERVER 2005/SQLSERVER 2008服务 •SQLSERVER jdbc驱动程序 •Java开发环境eclipse + jdk1.8 •java反编译工具JD-Core 反编译JDBC分析SQLSERVER客户端与服务器通信原理 SQ...

紅顏為君笑
今天
6
0
jQuery零基础入门——(六)修改DOM结构

《jQuery零基础入门》系列博文是在廖雪峰老师的博文基础上,可能补充了个人的理解和日常遇到的点,用我的理解表述出来,主干出处来自廖雪峰老师的技术分享。 在《零基础入门JavaScript》的时...

JandenMa
今天
0
0
linux mint 1.9 qq 安装

转: https://www.jianshu.com/p/cdc3d03c144d 1. 下载 qq 轻聊版,可在百度搜索后下载 QQ7.9Light.exe 2. 去wine的官网(https://wiki.winehq.org/Ubuntu) 安装 wine . 提醒网页可以切换成中...

Canaan_
今天
0
0
PHP后台运行命令并管理运行程序

php后台运行命令并管理后台运行程序 class ProcessModel{ private $pid; private $command; private $resultToFile = ''; public function __construct($cl=false){......

colin_86
今天
1
0
数据结构与算法4

在此程序中,HighArray类中的find()方法用数据项的值作为参数传递,它的返回值决定是否找到此数据项。 insert()方法向数组下一个空位置放置一个新的数据项。一个名为nElems的字段跟踪记录着...

沉迷于编程的小菜菜
今天
1
1
fiddler安装和基本使用以及代理设置

项目需求 由于开发过程中客户端和服务器数据交互非常频繁,有时候服务端需要知道客户端调用接口传了哪些参数过来,这个时候就需要一个工具可以监听这些接口请求参数,已经接口的响应的数据,这种...

银装素裹
今天
0
0
Python分析《我不是药神》豆瓣评论

读取 Mongo 中的短评数据,进行中文分词 对分词结果取 Top50 生成词云 生成词云效果 看来网上关于 我不是药神 vs 达拉斯 的争论很热啊。关于词频统计就这些,代码中也会完成一些其它的分析任...

猫咪编程
今天
0
0
虚拟机怎么安装vmware tools

https://blog.csdn.net/tjcwt2011/article/details/72638977

AndyZhouX
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部