[实践OK]传说中的冒泡排序法在PHP中实现及排序原理描述。

jackxiang 2012-8-10 23:42 | |
背景:在很多PHP面试上会给一些冒泡排序、或不说是冒泡排序,而说是自己实现一个按顺序排序,其实更高效呢需要更多时间写代码及思考,往往冒泡排序是最容易考察一个人对php也好,c的指针也好的一个驾驭以能力。

         经典的冒泡排序法一直是许多程序沿用的其中一种排序法,话说冒泡排序法在效率上比PHP系统函数sort更高效。本章不讨论性能,所以就不拿它来跟系统性能做对比了。


我写了一个,其原理,就是无论给一个什么样的数组,其输入这个排序函数,就给按数组下标小的值小在前面,而大的给放后面,也就是相当于一个瓶子里的气泡,轻的下沉,重的上浮,这个用语言讲出来还真不太好讲:
1)对于由a[0],a[1],a[2],a[3]....a[n-2],a[n-1],n个数组,通整个数组进行扫描(挨个扫:下标:0,1一组,1,2一组...,一组发现数组下标小的值且大的则交换),一直这样交换下去会发现:
(1)最大的那个经过一次扫描就沉到最下面了。
(2)最下面那个下一次不用再扫一次了,省一次比对。
  (3)根据2,对上面操作再扫一次,则这个倒数第二重的那个气泡也就排好了。
....依次类推,直至最上面两个数是最后一次,也就全排好了。(这个就是外层的一个:i最大,i--,因为内层一次后,最大那个已经到最下面了,于是,i--也就不用再扫它了)
12,45,28,30,88,67
第一次:12,28,30,45,67,88 //左右相邻比对,小下标大数值的往后挪
第二次:12,28,30,45,67,88 //这个其实一次就排好了,有些不规则的不止一次
.....
第N-1次 也就到了0,1两个下标的比对调整下位置,也就算排完了这个冒泡,确保正确。





---------- 调试PHP ----------
冒泡排序学习之PHP版本:Array
(
    [0] => 12
    [1] => 45
    [2] => 28
    [3] => 30
    [4] => 88
    [5] => 67
)
HeloArray
(
    [0] => 12
    [1] => 28
    [2] => 30
    [3] => 45
    [4] => 67
    [5] => 88
)

Output completed (0 sec consumed) - Normal Termination




下面这个是他人写的,感觉是反向,还不是太好理解,姑且放这儿吧:
冒泡排序大概的意思是依次比较相邻的两个数,然后根据大小做出排序,直至最后两位数。由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。但其实在实际过程中也可以根据自己需要反过来用,大树往前放,小数往后放。



通过以上代码执行结果

原数组Array ( [0] => 12 [1] => 45 [2] => 28 [3] => 30 [4] => 88 [5] => 67 )
排序后Array ( [0] => 88 [1] => 67 [2] => 45 [3] => 30 [4] => 28 [5] => 12 )

这就是冒泡法实例,简单吧!没有神马难度的

作者:jackxiang@向东博客 专注WEB应用 构架之美 --- 构架之美,在于尽态极妍 | 应用之美,在于药到病除
地址:http://jackxiang.com/post/5484/
版权所有。转载时必须以链接形式注明作者和原始出处及本声明!


最后编辑: jackxiang 编辑于2015-8-27 11:06
评论列表
2012-8-22 11:44 | root Email Homepage
楼上的认为会有多次做count的问题是么?
2012-8-21 14:34 | Adeploy Email Homepage
$k=count($arr)为嘛不放在外面。。。PHP和C差别不大吧
分页: 1/1 第一页 1 最后页
发表评论

昵称

网址

电邮

打开HTML 打开UBB 打开表情 隐藏 记住我 [登入] [注册]