一：什么是冒泡排序(升序)
(1)依次比较array[i]和array[i+1],如果array[i]大则交换位置,结果是最大的元素到达数组末尾,像气泡一样浮上来
(2)重复上述过程，去除最后一个元素，结果是次大的元素到达数组倒数第二的位置
(3)一次类推，重复n-1次即可
public function original_b_s($array)
{
$count = count($array);
$start_time = microtime(true);
for ($i = 1; $i < $count; ++$i)
{
for($j = 0; $j < $count - $i; ++$j)
{
if($array[$j] > $array[$j + 1])
{
list($array[$j] , $array[$j + 1]) = array($array[$j + 1], $array[$j]) ;
}
}
}
$end_time = microtime(true);
$message = 'eplaposed timie in '.__FUNCTION__.':'.($end_time - $start_time).'<br>';
echo $message;
}
我们可以想到这种极端情况：array本身就是排序好的，但是依照如上算法，我们仍然要遍历n平方/2次。原因在于，我们没有机制检查数组是否是排序好的。解决办法就是在每次冒泡过程中标记是否有相邻元素交换产生，无交换则表明排序完毕.
算法实现如下：
public function faster_b_s($array)
{
$count = count($array);
$start_time = microtime(true);
for ($i = 1; $i < $count; ++$i)
{
$exchange = false;
for($j = 0; $j < $count - $i; ++$j)
{
if($array[$j] > $array[$j + 1])
{
$exchange = true;
list($array[$j] , $array[$j + 1]) = array($array[$j + 1], $array[$j]) ;
}
}
if(!$exchange) break;
}
$end_time = microtime(true);
$message = 'eplaposed timie in '.__FUNCTION__.':'.($end_time - $start_time).'<br>';
echo $message;
}
我们再想象一种极端情况：array长度为n，但是只有第一个和第二个元素未排序，依照原始的冒泡排序仍然需要进行n-1此冒泡，其实只要一趟冒泡即可。原始的冒泡排序我们假定了第n趟冒泡的范围是0-(length-n).实际上第n趟的涉及范围取决于第n-1趟的最后交换位置,例如n-1次排序的最后交换位置是index，则表明index之后的元素都已经排序完毕，所以第n趟的涉及范围是0-index,只需要记录每一趟冒泡的最后交换位置.
算法实现如下：
public function fatest_b_s($array) { $count = count($array); $start_time = microtime(true); $mark = $count - 1; for ($i = 1; $i < $count; ++$i) { for($j = 0; $j < $mark; ++$j) { if($array[$j] > $array[$j + 1]) { //$exchange = true; list($array[$j] , $array[$j + 1]) = array($array[$j + 1], $array[$j]) ; $index = $j + 1; } } $mark = $index; } $end_time = microtime(true); $message = 'eplaposed timie in '.__FUNCTION__.':'.($end_time - $start_time).'<br>'; echo $message; }
结语：
算法描述以及‘优化’完毕。两次优化的原则就是限界剪枝，进行更少的操作 。那么看看结果如何。
用生成的随机数填充数组，并依次调用三个排序函数，结果如下
(1)1000数组元素排序
eplaposed timie in original_b_s:0.38794994354248
eplaposed timie in faster_b_s:0.41779398918152
eplaposed timie in fatest_b_s:0.38996005058289
(2)5000数组元素排序
eplaposed timie in original_b_s:10.363991975784
eplaposed timie in faster_b_s:11.036885023117
eplaposed timie in fatest_b_s:11.047054052353
(3)10000数组元素排序
eplaposed timie in original_b_s:45.779250144958
eplaposed timie in faster_b_s:48.629040002823
eplaposed timie in fatest_b_s:48.757740974426
实验结果很失败，两次优化都耗费了更多的时间。原因是两次优化的初衷都是考虑了比较特殊的情况，想要通过减少比较次数的方法减少耗时，但是却增加了标记的耗时。
哈哈，写到这里我又做了一组测试，很有意思。主要变动就是记录了三种算法的比较次数，结果如下:
eplaposed timie in original_b_s:38.264737129211
compare count in original_b_s:49995000
eplaposed timie in faster_b_s:41.45903301239
compare count in faster_b_s:49978710
eplaposed timie in fatest_b_s:39.778419017792
compare count in fatest_b_s:49972651
实验结果表明，优化后比较次数并没有减少太多，但是增加了标记的耗时，所以导致优化后耗时更多。