登录站点

用户名

密码

快速注册

PHP冒泡排序 、快速排序算法 详细解释及原理

已有 3112 次阅读  2012-02-03 20:21

<?php
/**
* 本示例文件可直接运行,如需要看结果请将其放在你的网站根目录下,并访问 http://你的网站/BubbleSort.php
* 这是一个很常见的排序算法,它的名字叫冒泡排序,这是一种最简单的排序算法。
* 本算法可对数字进行排序,也可以对字符串进行排序
* 看懂它的好处:你可以很牢固地掌握循环的用法。
* 以“//”开头的行为注释行(不包括“//”之前的部分),以“/*”开头,并以“*/”结尾的若干行也是注释,注释语句是不会被执行的。
*
* @param 传入的参数为一个待排序的数组 $str
* @return 返回参数为排序完成后的数组 $str
*/
function BubbleSort($str)
//定义一个名为BubbleSort的函数,它有一个参数叫$str,这个参数必须是一个数组,这个数组里包含需要排序的一系列字符。
{
for ($i=0;$i<count($str);$i++) //count($str)的功能为统计数组中的元素数量,并返回这个数量值
//第一层循环,外层循环,由于冒泡排序的原理为,每次都找最小(或每次都找最大,本例是演示每次都找最小的情况)的那个字符,找出一个最小(“大”)的字符算一次循环
{
for ($j=count($str)-2;$j>=$i;$j--)
//内层循环,本次循环控制找最小(“大”)数的操作,由于每次要找出最大的数,必须拿一个数和每一个数对比,所以也是一个内层的循环操作
{
if($str[$j+1]<$str[$j])
//比较,是$j+1位置的字符大,还是$j位置的字符比较大,如果$j位置的字符比较大,那么交换$str[$j+1]和$str[$j]以保证排列在前面的字符更小
{
$tmp = $str[$j+1]; //交换两个位置的东西,需要三个空位才能完成,就像交换一杯可乐和一杯牛奶需要另一个空杯子一样,$tmp可以说就是空杯子
$str[$j+1]=$str[$j];//类似,有一杯牛奶,一杯可乐,我们想用牛奶杯装可乐,可乐杯装牛奶的话,就得进行这样的操作……
$str[$j]=$tmp;//整个交换的过程可以描述为:先将牛奶倒入空杯,再将可乐倒入牛奶杯,然后再将原来空杯里的牛奶倒入可乐杯
}

}//内层循环每执行一次,就会多找出一个“最小”的字符(除了前面循环中已经找过了的)

}//数组里有N个字符的话,循环就重复N-1次,这样才能完成排序
return $str; //将排序后的结果返回,返回后跳出函数体,$str变量在内存中消失,而BubbleSort($str)的值就是$str所返回的值
}//函数体定义完成标志我们称之为 end of function BubbleSort($str)

$str = array(3,6,1,5,9,0,4,6,11);//组出一个存放随机序列的若干数字的数组
print_r(BubbleSort($str)); //调用函数体
?>

基本原理┃:两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。

算法过程┃:设想被排序的数组$arr[0..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,
从下往上扫描数组$arr时,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。

分享 举报