一帖看懂PHP面试必考题：什么是冒泡排序

[面试“必考题”]时，有几个问题是公司人员常常会提出的，针对这些问题好好准备，在时也就不会哑口无言，无言以对了，下面就面试十大必考题做出分析： (1)为什么想进本公司? 这通常是面试官最先问到的...+阅读

一帖看懂PHP面试必考题：什么是冒泡排序

//首先定义一个数组；// 计算数组的长度；$n =count($arr)；// 外层循环n-1for($h=0;$h//内层循环n-h-1 for($i=0;$i //判断数组大小，颠倒位置（从小往大排序，还是从大往小）if($arr[$i]>$arr[$i+1]){//定义空容器$kong，然后将两个判断中大的装进去 $kong=$arr[$i+1]；//大的这时就空了，然后将小的装进去 $arr[$i+1]=$arr[$i]；//然后将小的在装到空的进去。这就实现了从小往大排序，从大往小与此相反 $arr[$i]=$kong； } }}最后运行结果如下：php编程冒泡排序完整代码粘贴如下：//冒泡排序$arr=array(23,5,26,4,9,85,10,2,55,44,21,39,11,16,55,88,421,226,588);$n =count($arr);//echo $n;for($h=0;$hfor($i=0;$iif($arr[$i]>$arr[$i+1]){//判断数组大小，颠倒位置 $kong=$arr[$i+1]; $arr[$i+1]=$arr[$i]; $arr[$i]=$kong; } }}var_dump($arr);...

关于冒泡排序

没看懂你说什么，但是这样排序已经完成了。

当i=0时，内循环，会把a[0]~a[cnt-1]中最大的数放到a[0];

当i=1时，内循环，会把剩下a[1]~a[cnt-1]中最大的数放到a[1];

当i=2时，内循环，会把剩下a[2]~a[cnt-1]中最大的数放到a[2];

;;;;;

所以没一次内循环，都会把剩下的最大的书放到相应的地方。

拿你那个例子来说，a[0]=1,a[1]=2,a[2]=3,a[3]=4,a[4]=5

进行第一趟排序（i=0）:

内循环，j=1时，因为a=[0]

当j=2时，因为a[0]

当j=3时，因为a[0]

当j=4时，因为a[0]

所以第一趟排序后，已经把最大数放入a[0],

暂时的结果为：a[0]=5,a[1]=1,a[2]=2,a[3]=3,a[4]=4。

这就是所谓的冒泡，它每一趟都会找到最大/小的数。

再进行第二趟排序（i=1）：因为a[0]已经最大，所以不参与

内循环，j=2时，因为a=[1]

当j=3时，因为a[1]

当j=4时，因为a[1]

所以第二趟排序后，已经把剩余数中最大数放入a[1],

暂时的结果为：a[0]=5,a[1]=4,a[2]=1,a[3]=2,a[4]=3。

同理，

第三趟排序后，会把剩余数中最大数放入a[2],

暂时的结果为：a[0]=5,a[1]=4,a[2]=3,a[3]=1,a[4]=2。

第四趟排序后，会把剩余数中最大数放入a[3],

暂时的结果为：a[0]=5,a[1]=4,a[2]=3,a[3]=2,a[4]=1。

到这里已经排序完成了

冒泡排序问题。

冒泡排序是一种用时间换空间的排序方法，最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。在这种情况下，每一次比较都需要进行交换运算。举个例子来说，一个数列 5 4 3 2 1 进行冒泡升序排列，第一次大循环从第一个数（5）开始到倒数第二个数（2）结束，比较过程：先比较5和4,4比5小，交换位置变成4 5 3 2 1；比较5和3,3比5小，交换位置变成4 3 5 2 1……最后比较5和1,1比5小，交换位置变成4 3 2 1 5。这时候共进行了4次比较交换运算，最后1个数变成了数列最大数。

第二次大循环从第一个数（4）开始到倒数第三个数（2）结束。进行3次比较交换运算。

……

所以总的比较次数为 4 + 3 + 2 + 1 = 10次

对于n位的数列则有比较次数为（n-1） + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了最大的比较次数

而O(N^2)表示的是复杂度的数量级。举个例子来说，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相对10^8来说，10000小的可以忽略不计了，所以总计算次数约为0.5 * N^2。用O(N^2)就表示了其数量级（忽略前面系数0.5）。