php冒泡排序算法及原理详解 (附优化方案)

原创 木鱼  2017-09-13 07:30  阅读 163 次

重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

先附上冒泡排序的代码:

<?php 

// 冒泡排序 正序
function bubbleSort ( $arr )
{
	$count = count($arr);

	for ($i=1; $i < $count; $i++) { 

		for ($j=0; $j < $count-$i; $j++) { 
			
			if ($arr[$j] > $arr[$j+1]) {

			        // 交换算法
			        
				// ---小->大----

				// 先把小值 赋值给临时变量
				$tmp = $arr[$j+1];
				// 再把大值 赋值给小的值
				$arr[$j+1] = $arr[$j];
				// 再把临时变量(小值) 赋值给大值
				$arr[$j] = $tmp;
				// 结论就是: 俩个值交换位置 小的值在左边, 大的值在右边.
			}

		}
			
	}
	return $arr;
}

$arr = [3,2,6,4,1,7,8,0,9];

var_dump(bubbleSort($arr));

 

如果没接触过,乍一看可能会愣一下,但是不要慌,且听我们的分析。

 

分析过程

我们用自我问答的方式讲解一下其中你可能会不理解的地方。

 

1、为什么外层的$i=1 ?

    相信我, 这不是一个问题, 如果你改一改for循环的大于号小于号之类的, 你可以让他变成0或者任何数.

    由于$j=0, 而且数组最后一位数是不需要$arr[$j]这样比较的, 因为他是最后一位. 假设数组长度是9,第一次循环$i就是12345678, $j就是01234567

2、为什么内层循环要有一个$count-$i ?

    这其实是为了优化循环的次数, 如果你细心打印观察的话, 你就会发现, 当外层循环第一次循环结束后, 数组内的最大值, 必定在数组的最右边 (提供的代码是正序从小到大排的), 既然最大值已经在最右边了, 那不就可以内层循环的次数减去外层已经循环的次数了吗?

3、if里面的代码是什么 ?

    注释的已经很清楚了, 用一个临时变量存储数据, 然后大值赋给小值, 小值赋给大值。

 

优化

此处转自文章:  PHP实现排序算法----冒泡排序(Bubble Sort)

《大话数据结构》果然是本好书,还给我们介绍了冒泡排序算法的改进,这里我就直接搬它的陈述:

上面的冒泡排序算法是否还可以优化呢?答案是肯定的。试想一下,如果我们待排序的序列是{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 来实现这一算法的改进:

代码: 

<?php

// 冒泡排序
function bubbleSort ( $arr )
{
	$count = count($arr);
	$flag = TRUE;

	for ($i=1; ($i < $count) && $flag; $i++) { 
	
		$flag = FALSE;
		
		for ($j=0; $j < $count-$i; $j++) { 
			
			if ($arr[$j] > $arr[$j+1]) {

				// ---小->大----

				// 先把小值 赋值给临时变量
				$tmp = $arr[$j+1];
				// 再把大值 赋值给小的值
				$arr[$j+1] = $arr[$j];
				// 再把临时变量(小值) 赋值给大值
				$arr[$j] = $tmp;
				// 结论就是: 俩个值交换位置 小的值在左边, 大的值在右边.
				$flag = TRUE;
			}

		}	
		
	}
	
	return $arr;
}

$arr = [3,2,6,4,1,7,8,0,9];

var_dump(bubbleSort($arr));

本文地址:https://www.m5yu.com/bubble-sort.html
关注我们:请关注一下我们的微信公众号:扫描二维码,公众号:木鱼博客
版权声明:本文为原创文章,版权归 木鱼 所有,欢迎分享本文,转载请保留出处!

发表评论