程序员算法入门—排序冒泡

冒泡排序

原理:假设有一组数组,比较其数组里面相邻数值的大小,从小到大的顺序一一排列。

例如:  $arr = array(6,3,8,2,9,1);

$arr数组里有6个数据,按照两两比较大小如下,注意  比较轮数 和 每轮比较次数

  1. 6和3比较,结果:3 6 8 2 9 1

  2. 6和8比较,结果:3 6 8 2 9 1

  3. 8和2比较,结果:3 6 2 8 9 1

  4. 8和9比较,结果:3 6 2 8 9 1

  5. 9和1比较,结果:3 6 2 8 1 9

①轮总结:1、比较了5次,没有获得从小到大的排序;2、9冒出来了,②轮不用再比较

  1. 3和6比较,结果:3 6 2 8 1 9

  2. 6和2比较,结果:3 2 6 8 1 9

  3. 6和8比较,结果:3 2 6 8 1 9

  4. 8和1比较,结果:3 2 6 1 8 9

②轮总结:1、比较了4次,没有获得从小到大的排序;2、8冒出来了,③轮不用再比较

  1. 3和2比较,结果:2 3 6 1 8 9

  2. 3和6比较,结果:2 3 6 1 8 9

  3. 6和1比较,结果:2 3 1 6 8 9

③轮总结:1、比较了3次,没有获得从小到大的排序;2、6冒出来了,④轮不用再比较

  1. 2和3比较,结果:2 3 1 6 8 9

  2. 3和1比较,结果:2 1 3 6 8 9

④轮总结:1、比较了2次,没有获得从小到大的排序;2、3冒出来了,⑤轮不用再比较

  1. 2和1比较,结果:1 2 3 6 8 9

⑤轮总结:1、比较了1次,获得了从小到大的排序;2、2冒出来了,由于还剩一个,就不用再比较了,排序完成

 

经过①②③④⑤轮比较,得出结论:

对于一个长度为N的数组,我们需要排序 N-1 轮,每 i 轮 要比较 N-i 次。对此我们可以用双重循环语句,外层循环控制循环轮次,内层循环控制每轮的比较次数。其优点是:每比较一轮,都会少比较一次,都会冒出一个最大值。

 

用时间复杂度说:

1、如果我们的数据正序,只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值,即:Cmin=n-1;Mmin=0;所以,冒泡排序最好的时间复杂度为O(n)。

2、如果很不幸我们的数据是反序的,则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

冒泡排序总的平均时间复杂度为:O(n2) 。

 

ex:

<?php

  function mp($arr){
    $count = count($arr)
    $temp = 0;
    //外层控制排序轮次
    for($i=0;$i<$count-1;$i++){
       //内层控制每轮比较次数
       for($j=0;$j<$count-1-$i;$j++){
           if($arr[$j]>$arr[$j+1]){
              $temp      = $arr[$j];
              $arr[$j]   = $arr[$j+1]
              $arr[$j+1] = $temp;
           }
       }

     }
     return $arr;
}
$arr = array(6,3,8,2,9,1);
$res = mp($arr);
var_dump($res);

参考链接:

https://www.cnblogs.com/wgq123/p/6529450.html

http://www.cnblogs.com/shen-hua/p/5422676.html

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注