冒泡排序的实现和优化

昵称11350173 2012-12-21

展开全文

作者：韩忠康来自：传智播客php论坛http://bbs./thread-7145-1-1.html

冒泡排序：

假设数组的长度为N，数组的索引是由0开始。

依次比较相邻的两个数，如果前面的数大于后边的数则交换2个数。

及在一轮的比较中，依次取得第一个元素到倒数第二个元素，分别与其后相邻的元素进行比较，前面的元素大于后面的元素则交换。这样经过一轮的比较，最大的元素则交换到最后的的位置上。

下面继续按照相同的比较方式比较余下的N-1个元素。直到比较到最后一个元素。

按照冒泡排序的描述，容易写出程序语言，利用双重循环完成。外层循环控制比较的轮数，如果有N个元素，则需要比较N-1轮。内层循环控制每一轮内参与比较的次数，第一轮需要比较N-1次，第二轮需要比较N-2次，以此类推。

看代码：

下面是PHP代码实现：function bubbleSort1(&$arr) {

$len = count($arr);//取出数组长度

for($i=0; $i<$len-1; ++$i) {//轮数

for($j=0; $j<$len-$i-1; ++$j) {//每轮比较次数

if($arr[$j] > $arr[$j+1]) {

//交换

$temp = $arr[$j];

$arr[$j] = $arr[$j+1];

$arr[$j+1] = $temp;

}

//print_r($arr); echo ' ';//去掉注释查看

}

//echo '

}

return 1;

}

复制代码这样就按照冒泡的描述，完成了基本编码。

我们现在考虑以下上面的运行过程，

第一轮需要比较 N-1次，

第二轮需要比较 N-2次，

第i轮需要比较 N-i次，

由此可以看出这个算法的时间复杂度为O(n^2)。

注意：文档中的三个例子都使用的如下的测试数据：$arr = array(4, 7, 6, 3, 9, 5, 8);可以去掉程序中的注释查看比较结果。

在比较的过程中，其实是有些比较过程是可以省略。当在一轮的比较过程中如果没有发生交换，没有交换说明没有前面的元素大于后面元素的情况，意味着排序完成。

下面重写编写代码实现：function bubbleSort2(&$arr) {

$len = count($arr);//取出数组长度

$flag = true;//设置标志，默认为true，表示需要继续比较

for($i=0; $flag && $i<$len-1; ++$i) {//轮数，标志为真，继续比较

$flag=false;//将标志设为false，表示还没有发生交换

for($j=0; $j<$len-$i-1; ++$j) {//每轮比较次数

if($arr[$j] > $arr[$j+1]) {//交换

$temp = $arr[$j];

$arr[$j] = $arr[$j+1];

$arr[$j+1] = $temp;

$flag = true;//交换，设置为true表示需要继续比较

}

//print_r($arr);echo '

';//可以将注释去掉查看比较结果

}

//echo '

}

return 1;

}

复制代码上面的排序，会在某轮没有交换时，就比较完毕了：

例如：在上面的循环的第四轮，比较如下：

Array( [0] => 3 [1] => 4 [2] => 5 [3] => 6 [4] => 7 [5] => 8 [6] => 9) //第四轮后的比较的结果

Array( [0] => 3 [1] => 4 [2] => 5 [3] => 6 [4] => 7 [5] => 8 [6] => 9)

//比较后没有发生交换，则第五轮不需要再继续的，因此排序完成！优化过后，省去了2轮比较。

下面可以再看，我们上面记录的是否发生了交换，按照同样的思路，我们可以记录交换发生的最后位置。例如如果有5个元素没有排好顺序的话，但是在这五个元素比较时，如果第2个和第3个发生了交换，而后面2个的没有发生交换，说明后面的已经排好顺序了，那么在下次比较的时候就不需要在比较后面的3个元素了，直接比较到第2个元素即可。

这样还会省略掉几次比较次数：

再看编码实现：function bubbleSort3(&$arr) {

$len = count($arr);//取出数组长度

$flag = $len-1;//设置标志，默认为长度-2，表示需要比较到的位置

while($flag > 0) {

$pos = $flag;//设置需要比较到的位置，为上次的标志位

$flag = 0;//设置为0 表示没有发生交换，那么就说明不用再比较了

for($j=0; $j<$pos; ++$j) {//每轮比较次数,比较到最后交换的元素即可

if($arr[$j] > $arr[$j+1]) {//交换

$temp = $arr[$j];

$arr[$j] = $arr[$j+1];

$arr[$j+1] = $temp;