[常用算法PHP实现]之选择排序

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

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

[code lang=”php”]
//代码主要体现一下思想,没有对参数进行验证,比如是不是非空数组
function selectSort($arr,$sort=’asc’)
{
for($i = 0;$i<count($arr)-1;$i++){
for($j=$i+1;$j<count($arr);$j++){
if(($arr[$i]>$arr[$j]&&$sort==’asc’)||($arr[$i]<$arr[$j]&&$sort==’desc’)){
$temp = $arr[$j];
$arr[$j] = $arr[$i];
$arr[$i] = $temp;
}
}
}
return $arr;
}
[/code]

[常用算法PHP实现]之鸡尾酒排序

以下概念摘自维基百科:

鸡尾酒排序,也叫定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序,是冒泡排序的一种变形。不同的地方在于从低到高然后从高到低,而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要访问一次序列就可以完成排序,但如果使用冒泡排序则需要四次。 但是在乱数序列的状态下,鸡尾酒排序与冒泡排序的效率都很差劲,优点只有观念简单这一点

鸡尾酒排序最糟或是平均所花费的次数都是O(n^2),但如果序列在一开始已经大部分排序过的话,会接近O(n)

其实直接叫它双向冒泡排序就好了。

[code lang=”php”]
//如果代码行比较长,可以横向拖动下
function cocktailSort($arr,$sort=’asc’){
$sorted = false;
$bottom = 0;
$top = count($arr)-1;
while(!$sorted){
$sorted = true;
for ($i = $bottom; $i < $top; $i++) {
if(($arr[$i]>$arr[$i+1]&&$sort==’asc’)||($arr[$i]<$arr[$i+1]&&$sort==’desc’)){
$temp = $arr[$i+1];
$arr[$i+1] = $arr[$i];
$arr[$i] = $temp;
$sorted = false;//需要交换元素说明数组还没有被排序好
}
}

//然后再反向走一趟

//$top-1是因为拥有最大(小)值的元素已经在数组的顶端位置了
$top–;
for ($i = $top; $i > $bottom; $i–) {
if(($arr[$i]<$arr[$i-1]&&$sort==’asc’)||($arr[$i]>$arr[$i-1]&&$sort==’desc’)){
$temp = $arr[$i-1];
$arr[$i-1] = $arr[$i];
$arr[$i] = $temp;
$sorted = false;
}
}
//$bottom+1是因为是拥有最小(大)值得元素已经在数组的底部
$bottom++;
}
return $arr;
}
[/code]

[常用算法PHP实现]之奇偶排序

关于奇偶排序的概念线面摘抄一下维基百科的介绍:

奇偶排序,或奇偶换位排序,或砖排序[1],是一种相对简单的排序算法,最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序

该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换。下一步重复该操作,但针对所有的(偶-奇)位置数字对。如此交替进行下去。

以下是php版本的实现:

[code lang=”php”]
function addEvenSort($arr,$sort=’asc’){
$sorted = false;
while(!$sorted){
$sorted = true;
for($i = 1;$i < count($arr)-1;$i+=2){
if(($arr[$i]>$arr[$i+1]&&$sort==’asc’) || ($arr[$i]<$arr[$i+1] && $sort==’desc’)){
$temp = $arr[$i+1];
$arr[$i+1] = $arr[$i];
$arr[$i] = $temp;
$sorted = false;
}
}

for($i = 0;$i < count($arr)-1;$i+=2){
if(($arr[$i]>$arr[$i+1]&&$sort==’asc’) || ($arr[$i]<$arr[$i+1] && $sort==’desc’)){
$temp = $arr[$i+1];
$arr[$i+1] = $arr[$i];
$arr[$i] = $temp;
$sorted = false;
}
}
}
return $arr;
}
[/code]

[常用算法PHP实现]之插入排序

[code lang=”php”]
/**
* [insertSort 插入排序]
* @param [array] $arr [要排序的数组]
* @param [string] $sort ["desc" or "asc"]
* @return [array] [排序好的数组]
*/

function insertSort($arr,$sort){
foreach ($arr as $key => $value) {
$i = $key -1;//获取当前元素
//前面的元素如果比$value 大(小)统统向后挪动一个位置
if($sort==’asc’){
while ($i>-1 && $arr[$i] > $value) {
$arr[$i+1] = $arr[$i];
$i–;
}
}elseif($sort==’desc’){
while ($i>-1 && $arr[$i] < $value) {
$arr[$i+1] = $arr[$i];
$i–;
}
}
//将当前元素$value插入到新位置
$arr[$i+1] = $value;
}
return $arr;
}
[/code]

PHP 自动加载对象

如果定了很多类文件,在使用的时候常用的方法就是在文件包含这些类文件,但是如果类文件太多则是一个比较烦的事情,包含文件可能会写一坨

这里说一种常用的自动加载的方法

比如我们先定义一个类,文件名 a.php

[code lang=”php”]
<?php
class A{
private $var;

public function getVar()
{
return $this->var;
}

public function setVar($value=”)
{
$this->var = $value;
}
}
?>
[/code]
再定义另一个类文件c.php
[code lang=”php”]
<?php
class C{
function __toString(){
return "this is class C";
}
}
[/code]
然后在我们在 b.php 里使用自动加载方法
[code lang=”php”]
<?php
//先定义一个自动加载的function
function _autoload($class=”)
{
//简单演示,写的较简单
include_once(strtolower($class).".php");
}
//然后将函数注册到SPL __autoload函数栈中
spl_autoload_register(‘_autoload’);
$b = new A();
$b->setVar("have fun");
echo $b->getVar();//have fun

$b = new C();
echo $b;//this is a class C
[/code]

自动加载函数的名字是可以换的,比如

[code lang=”php”]
<?php
function example($class=”)
{
include_once(strtolower($class).".php");
}
spl_autoload_register(‘example’);
$b = new A();
$b->setVar("have a fun");
echo $b->getVar();//have a fun

$b = new C();
echo $b;//this is a class C
[/code]

文档里都有介绍,偶没深入写,若拍请轻拍

PHP单例模式

网上很多讲php单例模式的帖子,但是每个人讲的都会有差异。

要了解一个概念,我觉得首先要先看下官方的文档,如果官方文档里没有的再去搜索其他资料,比如这个单例模式,php官方文档里讲的又简单又清楚

这里贴一下phpdoc里的介绍

单例模式(Singleton)用于为一个类生成一个唯一的对象。最常用的地方是数据库连接。 使用单例模式生成一个对象后,该对象可以被其它众多对象所使用。

 

Example #2 单例模式

<?php
class Example
{
    
// 保存类实例在此属性中
    
private static $instance;
    
       
// 构造方法声明为private,防止直接创建对象
    
private function __construct() 
    {
        echo 
'I am constructed';
    }

    // singleton 方法
    
public static function singleton() 
    {
        if (!isset(
self::$instance)) {
            
$c __CLASS__;
            
self::$instance = new $c;
        }

        return self::$instance;
    }
    
    
// Example类中的普通方法
    
public function bark()
    {
        echo 
'Woof!';
    }

    // 阻止用户复制对象实例
    
public function __clone()
    {
        
trigger_error('Clone is not allowed.'E_USER_ERROR);
    }

}

?>

这样我们可以得到一个独一无二的Example类的对象。

<?php

// 这个写法会出错,因为构造方法被声明为private
$test = new Example;

// 下面将得到Example类的单例对象
$test Example::singleton();
$test->bark();

// 复制对象将导致一个E_USER_ERROR.
$test_clone = clone $test;

?>

Continue reading PHP单例模式