欢迎访问芦艺网!

冒泡排序算法的PHP实现

冒泡排序常常被用于程序设计课程的算法概念的介绍,在大学的《C语言》课程中,我们就做过冒泡排序的编程作业。冒泡排序算法的知名度其实还是很高的,不过算法的效率却不太理想。最坏的情况下冒泡排序的时间复杂度是O(n^2),最好的情况则是O(n)。其实现在已经有很多很好的排序算法来替代它,比如:插入排序、快速排序。不过冒泡排序作为经典的编程入门案例,还是值得一讲。首先,看一下使用冒泡排序为一列数字进行排序的过程,参照下图:

Bubble_sort_animation

冒泡排序算法的原理大致如下:
1. 交换:比较数列中相邻的元素,如果第一个比第二个大,就交换他们两个。
2. 比较:对每一对相邻元素都执行[交换],从开始第一对到结尾的最后一对。
3. 冒泡:每执行一遍,最大的数就会被排到数列的最后一位。
4. 循环:全部循环持续每次对越来越少的元素重复上面的步骤,直到所有元素已经排序好。

冒泡排序的算法PHP实现请参照以下代码:

function bubbleSort($numbers) {
   $cnt=count($numbers);
   for($i=0;$i<$cnt-1;$i++){//循环比较
       for($j=$i+1;$j<$cnt;$j++){
           if($numbers[$j]<$numbers[$i]){//执行交换
              $temp=$numbers[$i];
              $numbers[$i]=$numbers[$j];
              $numbers[$j]=$temp;
           }
       }
   }
   return $numbers;
}

$num = array(20, 40, 60, 80, 30, 70, 90, 10, 50, 0);
var_dump(bubbleSort($num));
//输出结果如下:
//array(10) { [0]=> int(0) [1]=> int(10) [2]=> int(20) [3]=> int(30) [4]=> int(40) [5]=> int(50) [6]=> int(60) [7]=> int(70) [8]=> int(80) [9]=> int(90) }

发表评论

关闭菜单