一,什么是冒泡算法
冒泡算法,是一种计算机科学领域里比较简单的排序算法。它需要重复的走访过要排序的数列,依次比较两个相邻的元素,如果顺序错误就进行交换,一直到没有相邻元素需要交换,即排序完成。
这个算法的名字由来是因为越小的元素经过交换之后,会慢慢的浮到数列的顶端,就像碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
二,冒泡算法的原理
冒泡排序算法的原理如下:
1,比较相邻的两个元素,如果第一个比第二个大,就交换他们两个;
2,对每一对相邻的元素做同样的动作,从开始的第一对到队尾的最后一对。在这一点,最后的元素应该是最大的数;
3,针对所有元素重复以上的动作,除了最后一个;
4,持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要交换;
三,排序过程
假如需要对给定的无序数组进行排序
第一轮排序
第一次排序,将指针放在队首位置,即9的位置,并与7进行比较,9比7大,所以9跟7交换位置
第二次排序,将指针往后移动,置于9的位置,并与1进行比较,9比1大,所以9跟1交换位置
第三次排序,将指针往后移动,置于9的位置,并与3进行比较,9比3大,所以9跟3交换位置
第四次排序,将指针往后移动,置于9的位置,并与2进行比较,9比2大,所以9跟2交换位置
到此,9已经处于队尾的位置,不需要再继续参与排序了,第一轮排序结束。
第二轮排序
第一次排序,将指针置于队首的位置,即7的位置,并与1进行比较,7比1大,所以7跟1交换位置
第二次排序,将指针往后移动,置于7的位置,并于3进行比较,7比3大,所以7跟3交换位置
第三次排序,将指针往后移动,置于7的位置,并于2进行比较,7比2大,所以7跟2交换位置
到此,7已经排好序,不需要再参与排序了,第二轮排序结束。
第三轮排序
第一次排序,将指针置于队首的位置,即1的位置,并与3进行比较,1比3小,所以1跟3不用交换位置
第二次排序,将指针往后移动,置于3的位置,并与2进行比较,3比2大,所以3跟2交换位置
到此,3已经排好序,不需要再参与排序了,第三轮排序结束
第四轮排序
第一次排序,将指针置于队首的位置,即1的位置,并与2进行比较,1比2小,所以1跟2不用交换位置
到此,1跟2已经排好序,排序结束。
四,PHP代码实现
function bubbleSort($array){
$count = count($array);
for ($i=0;$i<$count-1;$i++){
for ($j=0;$j<$count-$i-1;$j++) {
if($array[$j] > $array[$j+1]) {
$t = $array[$j];
$array[$j] = $array[$j+1];
$array[$j+1] = $t;
}
}
}
return $array;
}
上面代码利用了双循环来实现排序。 外循环用来控制所有轮次,内循环用来控制每一轮的排序。那上面的代码有没有可以优化的地方呢?我们来思考一个问题,假如所有数列都是有序的,那么第一轮第一次排序之后所有数列没有发生一次交换,这时候其实已经可以不用再继续后面的循环了,这样可以减少循环的次数。
我们可以做个小小的改动,在一轮排序之后,如果没有发生任何交换,即表明整个数列有序。
改动后的代码如下:
function bubbleSort($array){
$count = count($array);
for ($i=0;$i<$count - 1;$i++){
$isChange = false;
for ($j=0;$j<$count-$i-1;$j++) {
if($array[$j] > $array[$j+1]) {
$t = $array[$j];
$array[$j] = $array[$j+1];
$array[$j+1] = $t;
$isChange = true;
}
}
if(!$isChange) {
break;
}
}
return $array;
}
更多推荐
使用PHP实现冒泡排序
发布评论