PHP排序算法之冒泡排序(Bubble Sort)实现方法详解
本文实例讲述了PHP排序算法之冒泡排序(BubbleSort)实现方法。分享给大家供大家参考，具体如下：
基本思想：
冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
最简单排序实现：
我们先来看看在没有学习各种排序方法前经常使用的排序方法（至少我是这样。。。。）：
//这里使用了类型提示（typehint）array，不熟悉或者不习惯的同学大可去掉，不影响运算结果
functionMySort(array&$arr){
$length=count($arr);
for($i=0;$i<$length-1;$i++){
for($j=$i+1;$j<$length;$j++){
//将小的关键字放前面
if($arr[$i]>$arr[$j]){
$temp=$arr[$i];
$arr[$i]=$arr[$j];
$arr[$j]=$temp;
}
}
}
}
$arr=array(9,1,5,8,3,7,4,6,2);
MySort($arr);
print_r($arr);
上面的这段代码严格意义上说，不算是标准的冒泡排序，因为它不满足“两两比较相邻记录”的冒泡排序思想，它仅仅是一个简单的交换排序。思路不过是：从第一个关键字开始，将每一位关键字与它后面的所有关键字相比较，交换得到其中的最小值。但这个算法是非常低效的。
冒泡排序算法：
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为数组中越大的元素会由于一次次排序后逐渐“沉”到数组的后面，而越小的元素会逐渐“浮”到数组的前面，故名。
冒泡排序算法的运作如下：（从后往前）
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
看文字描述不一定看得懂，看代码吧：
//交换方法
functionswap(array&$arr,$a,$b){
$temp=$arr[$a];
$arr[$a]=$arr[$b];
$arr[$b]=$temp;
}
//冒泡排序
functionBubbleSort(array&$arr){
$length=count($arr);
for($i=0;$i<$length-1;$i++){
//从后往前逐层上浮小的元素
for($j=$length-2;$j>=$i;$j--){
//两两比较相邻记录
if($arr[$j]>$arr[$j+1]){
swap($arr,$j,$j+1);
}
}
}
}
冒泡排序算法改进：
《大话数据结构》果然是本好书，还给我们介绍了冒泡排序算法的改进，这里我就直接搬它的陈述：
上面的冒泡排序算法是否还可以优化呢？答案是肯定的。试想一下，如果我们待排序的序列是{2,1,3,4,5,6,7,8,9}，也就是说，除了第一和第二个关键字需要交换外，别的都已经是正常的顺序了。当i=0时，交换了2和1，此时的序列已经是有序的了，但是算法仍然不依不挠地将i=2到9以及每个循环中的j循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了。
当i=2时，我们已经对9与8，8与7，·······，3与2做了比较，没有任何数据交换，这就说明此序列已经有序，不需要再继续后面的循判断工作了（后面的工作也是不会发生任何数据交换，再做也是没有意义了）。为了实现这个想法，我们需要改进一下代码，增加一个标记变量flag来实现这一算法的改进：
//交换方法
functionswap(array&$arr,$a,$b){
$temp=$arr[$a];
$arr[$a]=$arr[$b];
$arr[$b]=$temp;
}
/冒泡排序的优化(如果某一次循环的时候没有发生元素的交换，则整个数组已经是有序的了)
functionBubbleSort1(array&$arr){
$length=count($arr);
$flag=TRUE;
for($i=0;($i<$length-1)&&$flag;$i++){
$flag=FALSE;
for($j=$length-2;$j>=$i;$j--){
if($arr[$j]>$arr[$j+1]){
swap($arr,$j,$j+1);
$flag=TRUE;
}
}
}
}
代码改动的关键就是在i变量的for循环中，增加了对flag是否为true的判断，经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断。
冒泡算法总的时间复杂度是O(n^2)。
冒泡排序是稳定排序。
本文参考自《大话数据结构》，在此仅作记录，方便以后查阅，大神勿喷！
PS：这里再为大家推荐一款关于排序的演示工具供大家参考：
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多关于PHP相关内容感兴趣的读者可查看本站专题：《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》
希望本文所述对大家PHP程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。