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

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

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

先附上冒泡排序的代码:

<?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));