请选择 进入手机版 | 继续访问电脑版

冒泡排序:从数学逻辑到代码呈现

[复制链接]
发表于 2019-4-10 14:45:21 |显示全部楼层
http://xuejava.org/thread-391-1-1.html
最近好多小伙伴问到冒泡排序如何写,忍不住上网查了一下,发现网上的资料大多只讲了代码呈现,但是并没有讲数学逻辑。其实这种代码,你首先要把数学逻辑弄懂了,然后再去转化计算机语言,只要懂相关语言的语法,不管怎么变语言,逻辑都不变。下面正式开始我们的主题。
1.冒泡排序的算法逻辑:
注:关键字是相邻元素,即冒泡排序是只针对2个挨着的元素比较的。然后每一趟找出最大的数。
2.数学逻辑
给你9个数,分别为:55,44,11,77,66,99,88,33,22。
0趟:
第0次:   44,55,11,77,66,99,88,33,22           (44和55比较,55大于44,故这2个调位置)
第1次:   44,11,55,77,66,99,88,33,22            ( 55和11比较,55大于11,故这2个调位置)
第2次:   44,11,55,77,66,99,88,33,22            ( 55和77比较 ,55<77,故位置不变)
第3次:   44,11,55,66,77,99,88,33,22           (77和66比较,77大于66,故这2个调位置)
第4次:   44,11,55,66,77,99,88,33,22           (77和99比较,77<99,故位置不变)
第5次:   44,11,55,66,77,88,99,33,22           (99和88比较,99大于88,故这2个调位置)
第6次:   44,11,55,66,77,88,33,99,22           (99和33比较,99大于33,故这2个调位置)
第7次:   44,11,55,66,77,88,33,22,99           (99和22比较,99大于22,故这2个调位置)
结果最大的99排在最后,第0趟结束,一共比较了8次
注:此次最大的已经在最后了,故以后不再比较99了。
1趟:
第0次:  11,44,55,66,77,88,33,22,99          (44和11比)
第1次:  11,44,55,66,77,88,33,22,99          (44和55比)
第2次:  11,44,55,66,77,88,33,22,99          (55和66比)
第3次:  11,44,55,66,77,88,33,22,99          (66和77比)
第4次:  11,44,55,66,77,88,33,22,99          (77和88比)
第5次:  11,44,55,66,77,33,88,22,99           (88和33比)
第6次:  11,44,55,66,77,33,22,88,99           (88和22比)
结果88和99占据高位,第1趟比较结束,一共比较了7次
注:此次88排在倒数第二位,此后88和99不再参加比较了。
2趟:
第0次:  11,44,55,66,77,33,22,88,99           (11和44比较)
第1次:  11,44,55,66,77,33,22,88,99          (44和55比较)
第2次:  11,44,55,66,77,33,22,88,99          (55和66比较)
第3次:  11,44,55,66,77,33,22,88,99          (66和77比较)
第4次:  11,44,55,66,33,77,22,88,99          (77和33比较)
第5次:  11,44,55,66,33,22,77,88,99          (77和22比较)
结果77,88,99占据高位,第2趟比较结束,一共比较6次
注:此次77排在倒数第三位,此后77,88,99不再参加比较了。
3趟:
第0次:   11,44,55,66,33,22,77,88,99          (11和44比较)
第1次:   11,44,55,66,33,22,77,88,99          (44和55比较)
第2次:   11,44,55,66,33,22,77,88,99          (55和66比较)
第3次:   11,44,55,33,66,22,77,88,99          (33和66比较)
第4次:   11,44,55,33,22,66,77,88,99          (66和22比较)
结果66,77,88,99占据高位,第3趟比较结束,一共比较5次
注:此次66排在倒数第四位,此后66,77,88,99不再参加比较了。
4趟:
第0次:    11,44,55,33,22,66,77,88,99         (11和44比较)
第1次:    11,44,55,33,22,66,77,88,99         (44和55比较)
第2次:    11,44,33,55,22,66,77,88,99         (55和33比较)
第3次:    11,44,33,22,55,66,77,88,99         (22和33比较)
结果55,66,77,88,99占据高位,第4趟比较结束,一共比较4次
注:此次55排在倒数第四位,此后55,66,77,88,99不再参加比较了。
5趟:
第0次:     11,44,33,22,55,66,77,88,99          (11和44比较)
第1次:     11,33,44,22,55,66,77,88,99          (44和33比较)
第2次:     11,33,22,44,55,66,77,88,99          (44和22比较)
结果44,55,66,77,88,99占据高位,第,5趟比较结束,一共比较3次
注:此次44排在倒数第五位,此后44,55,66,77,88,99不再参加比较了。
6趟:
第0次:     11,33,22,44,55,66,77,88,99           (11和33比较)
第1次:     11,22, 33,44,55,66,77,88,99            (33和22比较)
结果33,44,55,66,77,88,99占据高位,第6趟比较结束,一共比较2次
注:此次33排在倒数第六位,此后33,44,55,66,77,88,99不再参加比较了。
7趟:
第0次:       11,22, 33,44,55,66,77,88,99           (11和22比较)
结果22,33,44,55,66,77,88,99占据高位,第7趟比较结束,一共比较1次。
至此只剩下11一个数了,没得比了,其他元素都比它大,在自己位置乖乖呆着就是了,所以冒泡结束。
总结:上面红色的趟数就是我们第几轮对目前这一排数字进行相邻元素排序,每趟里面的次数代表相邻2个元素比较,每两个元素一比较算一次。
3.代码逻辑转换:
可以从第2步里面分析发现,主要是对几趟进行第几次的相邻2个元素比较,如果前面的数大于后面的数,则这2个位置互换,否则位置不变。
主要是2个值起作用,一个是第几趟,另一个是第几次,而第几次又是与第几趟关联的。故用i来表示第几趟,用j来表示第几次,发现i的取值为从0到n-2。
可以发现j的最大值是与i有关联的,即i+j的最大值为n-2。(n为长度)
4.代码呈现:
C语言:

运行结果:

注:此处我用的LR工具编译的,可能别的编译器会有所不同,基本思路一样。
图中的9就是这个元组的长度,lr中自定义函数一般放在action下面的。
python语言:

运行结果:
注:此处使用的pycharm工具编译的,其他工具方法应该类似。
到次冒泡结束。


您需要登录后才可以回帖 登录 | 立即注册

Archiver|手机版|沙漏笔记

GMT+8, 2019-6-24 16:50 , Processed in 0.146464 second(s), 20 queries .

Powered by Discuz! X2.5

© 2001-2012 Comsenz Inc.

Copyright © 2015-2018 xuejava网 / 鲁ICP备17054568号-1
回顶部