欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  php教程

冒泡排序以及遇到一个关于数组一大一小的问题

程序员文章站 2022-04-06 09:01:26
...

冒泡排序

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

冒泡排序算法的运作如下:(从后往前)

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

l 依次比较相邻的两个元素,消除逆序(逆序是数学上的概念,是成对出现的,比如50,30就是一对逆序,所谓的消除逆序,就是大的放后面,小的放前面)

l 这样,一轮比较下来,最大的那个数一对是在最后面!

l 然后,再继续新的一轮的比较,注意,刚才一轮后的最大值不再参与比较,这样,这一轮参与比较的数值就比上一轮少一个如此反复,直到最后只剩下两个数值比较为止

所以是一个双重循环,外层控制轮数,内层控制每轮比较的次数。

如果数组有n个元素,一共需要比较n-1轮,也就是外循环的次数!

补充一个其他知识点:

list — 把数组中的值赋给一些变量 ,从小到大,反过来赋值从大到小

冒泡排序以及遇到一个关于数组一大一小的问题

冒泡排序以及遇到一个关于数组一大一小的问题

下面说一下我写的冒泡排序,以及注释我自己对它的理解:

//冒泡排序,让数组从小到大依次排序
function maopao($arr){
    //双层循环,外层控制,$i代表循环的轮数,比较轮数等于数组的个数减1,$i
    for($i=1,$len=count($arr);$i){
        //内层控制每一轮比较的次数,$k=下标,每一轮比较完最后一个将不再参与比较,下标从0开始
        for($k=0;$k){
            //比较相邻的两个数,如果前面的数值比后面的大就调换下位置,通过中间数,如果不比它大,则不用调换
            if($arr[$k]>$arr[$k+1]){
                //调换位置
                $tem=$arr[$k];
                $arr[$k]=$arr[$k+1];
                $arr[$k+1]=$tem;
            }
        }
    }
    return $arr;
}
$arr1=array(45,85,12,22,36,7,75,15,40,64);
// echo count($arr1);
echo '
'; print_r(maopao($arr1));

冒泡排序以及遇到一个关于数组一大一小的问题

效果:实现了数组从小到大的排序

如果要实现从大到小,也是一样的算法,都是通过中间数的比较进行交换。

冒泡排序以及遇到一个关于数组一大一小的问题

接下来说一说我在面试曾遇到的一个问题:取一个数组,让这个数组按第一个最大,第二个最小,第三个第二大,第四个第二小…这样进行排序。

当时我只想到好像有个

array_pop:将数组的最后一个数据弹出

array_shift:从数组的前面弹出数据

那让数组从大到小排序后,弹出第一个就拿到最大的,弹出最后一个就拿到最小的,把这两个放一起就一个最大一个最小,再继续进行这样的取出,直到取完所有。

回去我就去尝试我这个可不可行,下面我就说下我自己试的这个方法

冒泡排序以及遇到一个关于数组一大一小的问题

冒泡排序以及遇到一个关于数组一大一小的问题

举例:

冒泡排序以及遇到一个关于数组一大一小的问题

冒泡排序以及遇到一个关于数组一大一小的问题

所以第一步:我是先让数组进行通过冒泡进行从大到小的排序

冒泡排序以及遇到一个关于数组一大一小的问题

第二步,我是通过递归把弹出来的第一个(最大)和最后一个(最小)放一起,再进行取出,直到取完为止。

冒泡排序以及遇到一个关于数组一大一小的问题

效果:

冒泡排序以及遇到一个关于数组一大一小的问题

冒泡排序以及遇到一个关于数组一大一小的问题

这个有更好的方法,我这里说的是我当时刚好想到的那个方法,哈,莫见怪,望吐槽。