注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

@fc_lamp

关注Web应用解决方案MySql/PHP/Python一盏名为"飞川"的灯~

 
 
 

日志

 
 

PHP排序呀????解析冒泡排序与快速排序?? PHP 递归函数??  

2013-09-22 18:13:29|  分类: Web技术-Php |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

<?php
/*
* 冒泡排序
* @author:fc_lamp
*
*/
function maopao($num)
{
$count = count($num);
if($count <=1)
{
return $num;
}

for($i=0;$i<=$count;$i++)
{
for($j=$i+1;$j<=$count-1;$j++)
{
if($num[$j]<$num[$i]) //换成>号即是倒序
{
$tmp = $num[$i];
$num[$i] = $num[$j]; //$num[$i]变成新值,继续内循环
$num[$j] = $tmp;
}
}
}
return $num;
}
$num = array(1,5,6,8,9,10,3,2,7,4);
var_dump(maopao($num));
/*

解析:


比如:当i为1时,$num[$i] = 5;当$num[6]=3时,条件成立,交换值。
数组如下:
array(1,3,6,8,9,10,5,2,7,4);
此在内循环(第二级),$num以 $num[$i]=3($i为1)来继续循环比较,此时数组下标(即$j)为7
当$num[$j] = 2时,条件也成立,数组如下:
array(1,2,6,8,9,10,5,3,7,4);
,现在$num[$i]=2 ($i为1)来继续循环比较,此时数组下标(即$j)为8
而后面的剩余的值为7,4都比3大,条件不成立。到此,外层循环结束(下一轮i 为2),数组值为:
array(1,2,6,8,9,10,5,3,7,4);

*/


快速排序是二分查找与递归的应用。

/**
*
* 快速排序
* @fc_lamp
*
*/
function quickSort($num)
{
$count = count ( $num );
if ($count <= 1)
{
return $num;
}
$key = $num [0];
$left_array = $right_array = array ();
unset ( $num [0] );
foreach ( $num as $v )
{
if ($v >= $key)
{
$right_array [] = $v;
} else
{
$left_array [] = $v;
}
}
//递归(类似二分查找)
#递归001
$left_array = quickSort ( $left_array );
#递归002
$right_array = quickSort ( $right_array );

return array_merge ( $left_array, array ($key ), $right_array );
}

$num = array (5, 1, 6, 8, 9, 10, 3, 2, 7, 4 );
var_dump ( quickSort ( $num ) );

/*

解析:


* 一切递归前:
* $key = 5;
* $left_array = array(1,3,2,4);
* $right_array = array(6,8,9,10,7);
*
* 递归001递归:
*
* 当执行"递归001"第一次递归 $left_array = quickSort ( $left_array );
* "递归001"递归后(编码: 递归001-1-1):
* $key = 1;
* $left_array = array();
* $right_array = array(3,2,4);
*
* 再执行"递归001"第二次递归:$left_array = quickSort ( $left_array );
* 由于$left_array已经是空的数组了(编码: 递归001-1-2),所以直接返回。
*
* 函数回到"递归001-1-1"状态下,执行"递归002"递归
* $right_array = array(3,2,4);
* $right_array = quickSort ( $right_array );
* "递归002"第一次递归后(编码: 递归001-2-1):
* $key = 3;
* $left_array = array(2);
* $right_array = array(4);
*
* 接着执行"递归001-2-1"状态下的"递归001"递归:
* $left_array = array(2);
* $left_array = quickSort ( $left_array );
* 由于$left_array 数组元素小于等于1(编码: 递归001-2-2),所以直接返回。
*
* 此函数返回到 "递归001-2-1"状态下:
* $key = 3;
* $left_array = array(2);
* $right_array = array(4);
*
* 紧接着执行"递归001-2-1"状态下的"递归002"递归:
* 同样的道理由于$right_array 数组元素小于等于1(编码: 递归001-2-3),所以直接返回。
* 此函数返回到 "递归001-2-1"状态下:
* $key = 3;
* $left_array = array(2);
* $right_array = array(4);
*
* 接着执行:
* array_merge ( $left_array, array ($key ), $right_array );
* 返回:
* array(2,3,4);
*
* 此函数回到了"递归001-1-1"状态下:
*
* $key = 1;
* $left_array = array();
* $right_array = array(2,3,4);
*
* 接着执行:
* array_merge ( $left_array, array ($key ), $right_array );
* 返回:
* array(1,2,3,4);
*
*
* 此函数回到了最顶层函数的状态下:
*
* $key = 5;
* $left_array = array(1,2,3,4);
* $right_array = array(6,8,9,10,7);
*
* 按照上面同样的道理执行 递归002递归。
* 最后得出结果。
*
*/


如果你对递归不太清楚,请看 (来源:http://www.it163.org/post/118fd1_76cc2f):

function test($n)
{

echo $n . " ";

if ($n > 0)
{

test ( $n - 1 );

} else
{
echo "<-->";
}

echo $n . " ";
}
test ( 10 ); //输出:10 9 8 7 6 5 4 3 2 1 0 <--> 0 1 2 3 4 5 6 7 8 9 10

原理如下:
第一步,执行test(10),echo 10,然后因为10>0,执行test(9),后面还有没来得及执行的echo 10
第二步,执行test(9),echo 9,然后因为9>0,执行test(8),同样后面还有没来得及执行的 echo 9
第三步,执行test(8),echo 8,然后因为8>0,执行test(7),同样后面还有没来得及执行的 echo 8
第四步,执行test(7),echo 7,然后因为7>0,执行test(6),同样后面还有没来得及执行的 echo 7
第五步,执行test(6),echo 6,然后因为6>0,执行test(5),同样后面还有没来得及执行的 echo 6
...........
第十步,执行test(0),echo 0,此时0>0的条件不满足,不在执行test()函数,而是echo “<-->”,并且执行后面的 echo 0
10 9 8 7 6 5 4 3 2 1 0 <--> 0 1 2 3 4 5 6 7 8 9 10
此时,输出的内容如上述显示的红色部分,此时函数已经不再调用自己,开始将流程的主控权交回给上一层函数来执行。

再看一个例子:

function three($num)
{
echo $num . ' ';
}

function two($num)
{
echo $num . ' ';
three ( $num - 1 );
echo $num . ' ';
}

function one($num)
{
echo $num . ' ';
two ( $num - 1 );
echo $num . ' ';
}
one(3);//输出 3 2 1 2 3

原理如下:
以上代码对test()函数进行分解操作,我们思考:
执行one(3)函数的时候,同test()函数一样,首先要输出3,然后调用two(2)函数,
注意,此时还没有输出下面的3,
接着走,执行two(2)函数,输出2,调用three(1)函数,同样,这里没有来得及输出下面的2,
执行three(1),直接输出1,不在调用其它函数,
此时,我们想刚刚的two()函数是不是还没有执行完,好,接着执行two()函数没有完成的部分,two()函数执行完之后,也就是输出下面的2,然后开始执行one()函数没有执行完的部分,也就是输出下面的3,此时所有函数执行完毕。



附:PHP内置的排序函数(以下函数全是引用传值)

http://cn2.php.net/manual/zh/array.sorting.php

sort 不保持键名的升序排。

rsort 不保持键名的降序排。

asort 保持键名的升序排。

arsort 保持键名的降序排。

ksort 按照键名排序(当然键名仍然存在的)。

krsort 按照键名的降序排。

usort 使用用户自定义的比较函数(usort($a, "cmp");)

uasort 使用用户自定义的比较函数,保持键名。

uksort 使用用户自定义的比较函数,按照键名比较。

natsort 用“自然排序”算法对数组排序

natcasesort 用“自然排序”算法对数组进行不区分大小写字母的排序

shuffle 将数组打乱

















  评论这张
 
阅读(398)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017