【院刊】-【201408期】游戏扫拍卖行（排序算法之冒泡法） _ 学院院刊

查看: 75496\|回复: 184	[技术交流] 【院刊】-【201408期】游戏扫拍卖行（排序算法之冒泡法） [复制链接]

果果。。

组别初中一年级
UID2314582
帖子240
精华0
鲜花358 朵
铜币1358 个
银币49 个
在线时间1920
注册时间2013-12-26

1^#

字体大小: t T

发表于 2014-08-27 18:53 | |只看楼主

排序算法之冒泡法—游戏扫拍卖行

作者：267-haiye（按键学院基础班学员） 编辑：果果。。

什么情况下会用到冒泡排序呢？例如，学生考试成绩的排列，财务部门支出清单的排序……等等。实现将一堆凌乱无序的东西，按照从大到小或者从小到大的顺序排列好，同时也能得知其中的最大值和最小值。

今天呢，我们借助游戏中的拍卖行，来讲解下如何用冒泡排序来实现。

算法原理:

冒泡排序（BubbleSort）

冒泡排序是最慢的排序算法，但也是新手最容易上手的一个排序方法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。

算法的复杂度

有没有同学问，O(n^2)的算法是什么呢？这是其实是衡量算法速度快慢的一个指标，我们称之为算法的时间复杂度。时间复杂越大，算法的执行效率越低。

当然，并不是越快的算法，一定越好。算法还有另一个指标，叫空间复杂度，即算法占用多少空间，这个和内存息息相关。一个算法可能很快，但是它占用的内存多，不一定耗得起。

所以呢在不同的场合，我们需要根据不同的要求，会选择最合适的算法。

如何计算时间复杂度

时间复杂度，其实就是算法中某一语句循环执行的次数。

例如：冒泡排序法的原理

For i = 1 To n
For j = 1 To n
冒泡排序
Next
Next

复制代码

这个算法的时间复杂度，即“冒泡排序”这个语句的执行次数。

当i=1的时候，For j = 1 To n:冒泡排序:Next，“冒泡排序”这个语句被执行了n次。

当i=2的时候，For j = 1To n:冒泡排序:Next，“冒泡排序”这个语句又被执行了n次。

当i=3的时候，For j = 1To n:冒泡排序:Next，“冒泡排序”这个语句又被执行了n次。

……

当i=n的时候，For j = 1To n:冒泡排序:Next，“冒泡排序”这个语句又被执行了n次。

综上，“冒泡排序”这个语句被执行了n个n次，即n*n=n^2次。所以冒泡排序的时间复杂度即为n^2，我们记为O（n^2）

注：1.如果算法中语句执行次数为一个常数，则时间复杂度为O(1)。

2.若一个算法的时间复杂度为O(n)=n^2+3n+4，我们只取算式中最高次方，即O(n^2)。

算法的实现

: 您所在的用户组无法下载或查看附件

算法讲解：

'冒泡排序
//经过n-1趟子排序完成的,它的时间复杂度为O（n^2）
//优点：1.代码简单易懂；2.具有稳定性

1.获取到物品价格，存入数组su

2.获取到数组的个数，即物品的总数，记为M

3.循环开始

4.获取到数组su(0)的数值

5.su(0)与数组中剩余的数值对比(su(1)-su(M))，若数值大于su(0)，则相互调换

6.Su(0)存储数组中最大的值

7.循环到数组最后一个数值su(M)

8.结束第一次循环，数组的第一个元素su(0)为数组中最大值

9.从su(1) 到su(M)，重复5-8步骤，实现su数组最后为从大到小的降序排列。

代码具体实现：

Dim i,j
su= "105875|502150|411400|63525|111925|90750" //获取到的物品价格
su=Split(su, "|")
M = UBound(su)
//升序排序
For i = 0 To UBound(su)-1 //i=0 的时候 j循环是从 1循环到数组最小不第一轮循环，su（0）和su (1）-su(5)进行比较选择6个数中最小的数放到su（0）第二轮循环 su（1）和su（2）-su（5）比较
For j = i+1 to UBound (su)
If int(su(i)) > int (su(j)) Then // 数组是字符串的所以需要用int改为数值型否则会出现错误
tran = su(j)
su(j) = su(i)
su(i) = tran //如果前一个数比后一个数大，就交换位置
End If
Next
Next
// 降序排序
For i = 0 To UBound(su)-1
For j = i+1 to UBound (su)
If int(su(i))
tran = su(j)
su(j) = su(i)
su(i) = tran //如果后一个数比前一个数大，就交换位置
End If
Next
Next

复制代码

代码的每一次实现

原数组： "105875|502150|411400|63525|111925|90750"

第一次循环：
取su(0)的值105875，与su(1)对比。su(1)>su(0)，则相互交换：

"502150|105875|411400|63525|111925|90750"

然后拿su(0)的值502150，与su(2)-su(5)对比，没有比su(0)更大的值，不再交换，结束。

第一次循环结束："502150|105875|411400|63525|111925|90750"

第二次循环：

取su(1)的值105875，与su(2)的值411400对比，su(2)>su(1)，则相互交换：

"502150|411400|105875|63525|111925|90750"

然后拿su(1)的值411400，与su(3)-su(5)对比，没有比su(1)更大的值，不再交换，结束。

第二次循环结束："502150|411400|105875|63525|111925|90750"

第三次循环：

取su(2)的值105875，与su(3)的值63525对比，su(3)
su(2)的值105875与su(4)的值111925对比，su(4)>su(2)，则相互交换：

"502150|411400|111925|63525|105875|90750"

然后拿su(2)的值111925，与su(5)的值90750对比，su(5)

第三次循环结束："502150|411400|111925|63525|105875|90750"

第四次循环：

取su(3)的值63525，与su(4)的值105875对比，su(4)>su(3)，相互交换：

"502150|411400|111925|105875|63525|90750"

取su(3)的值105875，与su(5)对比，su(5)

第四次循环结束："502150|411400|111925|105875|63525|90750"

第五次循环：

取su(4)的值63525，与su(5)的值90750对比，su(4)>su(5)，相互交换，循环结束。

第五次循环结束："502150|411400|111925|105875|90750|63525"

此时数组已循环到最后，完成降序排列。

知识拓展

按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

附上大大写好的冒泡排序VBS，各位大大可以直接调用使用哦~~

: 您所在的用户组无法下载或查看附件

调用方法：

Include "C:\冒泡排序.vbs" //地址是下载的冒泡排序vbs的所在地址
maopao su,1 // 语法： maopao 数组名称,升序或降序（1是升序，2是降序）
Sub Include(tz_var_file) //添加这段调用代码
Dim tz_var_fso, tz_var_f, tz_var_s
Set tz_var_fso = CreateObject("Scripting.FileSystemObject")
Set tz_var_f = tz_var_fso.OpenTextFile(tz_var_file)
tz_var_s = tz_var_f.ReadAll
Call tz_var_f.Close()
Call ExecuteGlobal(tz_var_s)
Set tz_var_fso = Nothing
End Sub

复制代码

往期相关院刊：
【院刊】-【201408期】计算距离自己最近的怪物/包裹/金矿坐标
【院刊】-【201408期】比冒泡更快的排序算法（快速排序）

本文由按键学院提供技术支持
按键学院实战班（即将入驻最终幻想）火热招生
按键学院基础视频抢先观看

已有7评分我要评分查看所有评分

本主题由超级版主瑞祥幽冥狼于 2023/7/23 18:21:35 执行审核帖子操作

按键学院交流群（开放中）：376122403 
 
<a href="http://bbs.anjian.com/thread-548439-1-1.html" target="_blank">按键学院开班 【安卓导师】+【实战导师】招聘导师啦~~待遇特别好，有钱，就是任性。 </a> 
 
 
<a href="http://bbs.anjian.com/t

回顶部

发送短消息 UID 131178 帖子 27 精华 0 鲜花 -1 朵铜币 45 个银币 -1 个性别在线时间 680 注册时间 2007-04-03 最后登录 2016-06-07 查看公共资料搜索主题搜索帖子 kdjabc5678 kdjabc5678 组别小学一年级 UID131178 帖子27 精华0 鲜花-1 朵铜币45 个银币-1 个在线时间680 注册时间2007-04-03	2^# 字体大小: t T 发表于 2016-04-28 15:14 \| \|只看该用户看看学习学习


	回顶部

发送短消息 UID 3987301 帖子 29 精华 0 鲜花 0 朵铜币 102 个银币 0 个性别在线时间 500 注册时间 2016-06-26 最后登录 2022-09-29 查看公共资料搜索主题搜索帖子 a344822316 组别小学一年级 UID3987301 帖子29 精华0 鲜花0 朵铜币102 个银币0 个在线时间500 注册时间2016-06-26	3^# 字体大小: t T 发表于 2016-06-28 17:33 \| \|只看该用户我要看


	回顶部

发送短消息 UID 3948216 帖子 101 精华 0 鲜花 -3 朵铜币 345 个银币 157 个性别在线时间 3160 注册时间 2016-06-01 最后登录 2021-07-29 查看公共资料搜索主题搜索帖子 j342233180 仙人掌组别小学五年级 UID3948216 帖子101 精华0 鲜花-3 朵铜币345 个银币157 个在线时间3160 注册时间2016-06-01 按键精灵开发者4级可通过提升认证等级来升级勋章：rz.anjian.com	4^# 字体大小: t T 发表于 2016-06-28 21:28 \| \|只看该用户冒泡排序


	回顶部

发送短消息 UID 3867309 帖子 432 精华 0 鲜花 74 朵铜币 1009 个银币 252 个性别在线时间 4220 注册时间 2016-04-14 最后登录 2024-03-02 查看公共资料搜索主题搜索帖子枫落ye无痕枫落ye无痕组别初中三年级 UID3867309 帖子432 精华0 鲜花74 朵铜币1009 个银币252 个在线时间4220 注册时间2016-04-14	5^# 字体大小: t T 发表于 2016-07-06 14:21 \| \|只看该用户 2222222222222222


	回顶部

发送短消息 UID 1850457 帖子 136 精华 0 鲜花 0 朵铜币 324 个银币 1 个性别在线时间 960 注册时间 2013-05-28 最后登录 2022-03-23 727946620 查看公共资料搜索主题搜索帖子狼牙啸天狼牙啸天组别小学六年级 UID1850457 帖子136 精华0 鲜花0 朵铜币324 个银币1 个在线时间960 注册时间2013-05-28	6^# 字体大小: t T 发表于 2016-07-08 03:12 \| \|只看该用户学习学习学习学习学习！


	回顶部

发送短消息 UID 4013856 帖子 4 精华 0 鲜花 0 朵铜币 23 个银币 1 个性别在线时间 20 注册时间 2016-07-14 最后登录 2023-12-14 查看公共资料搜索主题搜索帖子 463524003 组别小学一年级 UID4013856 帖子4 精华0 鲜花0 朵铜币23 个银币1 个在线时间20 注册时间2016-07-14	7^# 字体大小: t T 发表于 2016-07-14 08:04 \| \|只看该用户 sadsadsaasd


	回顶部

发送短消息 UID 593529 帖子 1138 精华 0 鲜花 225 朵铜币 1126 个银币 268 个性别在线时间 42840 注册时间 2011-02-06 最后登录 2024-05-07 464806020 查看公共资料搜索主题搜索帖子 ym169019 指尖跳舞组别大学二年级 UID593529 帖子1138 精华0 鲜花225 朵铜币1126 个银币268 个在线时间42840 注册时间2011-02-06 单身汪勋章单身贵族的专属勋章幸运草勋章商业小精灵限时活动勋章。马年勋章马年纪念勋章认证考霸对按键认证题目有深入研究，并且孜孜不倦学到老考到老黄瓜勋章体验商业小精灵活动的奖励按键明星按键明星勋章骨灰级按键用户 3年以上的按键论坛用户学有所成学有所成勋章，新手步入按键学堂的第一枚勋章按键精灵开发者6级可通过提升认证等级来升级勋章：rz.anjian.com	8^# 字体大小: t T 发表于 2016-07-15 00:27 \| \|只看该用户学习！！！！！！！！！！！！！！！！


	回顶部

发送短消息 UID 4042922 帖子 32 精华 0 鲜花 0 朵铜币 86 个银币 0 个性别在线时间 660 注册时间 2016-08-01 最后登录 2019-12-01 734843327 查看公共资料搜索主题搜索帖子 734843327 734843327 组别小学二年级 UID4042922 帖子32 精华0 鲜花0 朵铜币86 个银币0 个在线时间660 注册时间2016-08-01	9^# 字体大小: t T 发表于 2016-08-02 00:48 \| \|只看该用户 111111111111


	回顶部

发送短消息 UID 3920706 帖子 1454 精华 0 鲜花 37 朵铜币 2347 个银币 18 个性别在线时间 48480 注册时间 2016-05-16 最后登录 2022-11-13 查看公共资料搜索主题搜索帖子 kugeniha kugeniha 组别大学三年级 UID3920706 帖子1454 精华0 鲜花37 朵铜币2347 个银币18 个在线时间48480 注册时间2016-05-16 按键X开拓者勋章按键精灵X版开拓者勋章按键剑侠客按键剑侠客勋章过大年勋章俩小福娃给大家拜年啦！天使勋章天使一样的用户按键明星按键明星勋章按键精灵开发者6级可通过提升认证等级来升级勋章：rz.anjian.com 论坛GG 按键论坛男性用户勋章小红帽对论坛提出良好建议（可向管理员申请）发帖高手鼓励积极回复，但注意不要灌水哦	10^# 字体大小: t T 发表于 2016-08-04 18:24 \| \|只看该用户看看


	回顶部

发送短消息 UID 3196632 帖子 180 精华 0 鲜花 5 朵铜币 279 个银币 7 个性别在线时间 3700 注册时间 2015-04-15 最后登录 2023-12-01 查看公共资料搜索主题搜索帖子 anjians600 anjians600 组别初中一年级 UID3196632 帖子180 精华0 鲜花5 朵铜币279 个银币7 个在线时间3700 注册时间2015-04-15	11^# 字体大小: t T 发表于 2016-08-06 12:30 \| \|只看该用户 1212121212


	回顶部

发送短消息 UID 888695 帖子 207 精华 0 鲜花 1 朵铜币 420 个银币 158 个性别在线时间 4560 注册时间 2011-11-21 最后登录 2016-11-09 524387537 查看公共资料搜索主题搜索帖子 5831510 5831510 组别初中一年级 UID888695 帖子207 精华0 鲜花1 朵铜币420 个银币158 个在线时间4560 注册时间2011-11-21 按键精灵开发者1级可通过提升认证等级来升级勋章：rz.anjian.com 按键精灵开发者2级可通过提升认证等级来升级勋章：rz.anjian.com 按键精灵开发者3级可通过提升认证等级来升级勋章：rz.anjian.com 按键精灵开发者4级可通过提升认证等级来升级勋章：rz.anjian.com	12^# 字体大小: t T 发表于 2016-08-10 14:32 \| \|只看该用户 000000001111111112


	回顶部

发送短消息 UID 3883893 帖子 147 精华 0 鲜花 2 朵铜币 545 个银币 7 个性别在线时间 2660 注册时间 2016-04-24 最后登录 2021-11-01 查看公共资料搜索主题搜索帖子 18077629221 组别小学六年级 UID3883893 帖子147 精华0 鲜花2 朵铜币545 个银币7 个在线时间2660 注册时间2016-04-24	13^# 字体大小: t T 发表于 2016-08-11 20:10 \| \|只看该用户


	回顶部

发送短消息 UID 1925238 帖子 209 精华 0 鲜花 -1 朵铜币 441 个银币 159 个性别在线时间 9840 注册时间 2013-06-19 最后登录 2024-05-13 397611711 查看公共资料搜索主题搜索帖子 meichuan000 meichuan000 组别初中一年级 UID1925238 帖子209 精华0 鲜花-1 朵铜币441 个银币159 个在线时间9840 注册时间2013-06-19 按键精灵开发者6级可通过提升认证等级来升级勋章：rz.anjian.com	14^# 字体大小: t T 发表于 2016-08-12 06:46 \| \|只看该用户 kankanttt


	回顶部

发送短消息 UID 1925238 帖子 209 精华 0 鲜花 -1 朵铜币 441 个银币 159 个性别在线时间 9840 注册时间 2013-06-19 最后登录 2024-05-13 397611711 查看公共资料搜索主题搜索帖子 meichuan000 meichuan000 组别初中一年级 UID1925238 帖子209 精华0 鲜花-1 朵铜币441 个银币159 个在线时间9840 注册时间2013-06-19 按键精灵开发者6级可通过提升认证等级来升级勋章：rz.anjian.com	15^# 字体大小: t T 发表于 2016-08-12 06:46 \| \|只看该用户 kank@ngft


	回顶部

发送短消息 UID 4019131 帖子 30 精华 0 鲜花 0 朵铜币 68 个银币 0 个性别在线时间 860 注册时间 2016-07-17 最后登录 2016-08-24 377968150 查看公共资料搜索主题搜索帖子 18691968685 18691968685 组别小学二年级 UID4019131 帖子30 精华0 鲜花0 朵铜币68 个银币0 个在线时间860 注册时间2016-07-17	16^# 字体大小: t T 发表于 2016-08-13 01:12 \| \|只看该用户 123456


	回顶部

发送短消息 UID 3626451 帖子 169 精华 0 鲜花 0 朵铜币 504 个银币 0 个性别在线时间 6220 注册时间 2015-12-04 最后登录 2017-05-25 查看公共资料搜索主题搜索帖子 aarry 组别初中一年级 UID3626451 帖子169 精华0 鲜花0 朵铜币504 个银币0 个在线时间6220 注册时间2015-12-04	17^# 字体大小: t T 发表于 2016-08-16 17:59 \| \|只看该用户多谢楼主分享


	回顶部

发送短消息 UID 4042142 帖子 88 精华 0 鲜花 0 朵铜币 233 个银币 60 个性别在线时间 1860 注册时间 2016-08-01 最后登录 2017-06-29 查看公共资料搜索主题搜索帖子 anzhongzijian 组别按键精灵会员 UID4042142 帖子88 精华0 鲜花0 朵铜币233 个银币60 个在线时间1860 注册时间2016-08-01 按键精灵开发者3级可通过提升认证等级来升级勋章：rz.anjian.com	18^# 字体大小: t T 发表于 2016-08-17 15:47 \| \|只看该用户学习


	回顶部

发送短消息 UID 4067822 帖子 62 精华 0 鲜花 -1 朵铜币 82 个银币 -1 个性别在线时间 1840 注册时间 2016-08-14 最后登录 2016-08-27 837222368 查看公共资料搜索主题搜索帖子 15258764137a 15258764137a 组别小学三年级 UID4067822 帖子62 精华0 鲜花-1 朵铜币82 个银币-1 个在线时间1840 注册时间2016-08-14	19^# 字体大小: t T 发表于 2016-08-17 22:19 \| \|只看该用户刚给他


	回顶部

发送短消息 UID 1446907 帖子 456 精华 0 鲜花 3 朵铜币 1519 个银币 148 个性别在线时间 14480 注册时间 2012-11-25 最后登录 2023-10-27 258029276 查看公共资料搜索主题搜索帖子迷途军师迷途军师组别按键忠义之士 UID1446907 帖子456 精华0 鲜花3 朵铜币1519 个银币148 个在线时间14480 注册时间2012-11-25 按键精灵开发者5级可通过提升认证等级来升级勋章：rz.anjian.com	20^# 字体大小: t T 发表于 2016-08-19 03:07 \| \|只看该用户感谢分享啊,又来看看哦


	回顶部

上一主题| 下一主题

[技术交流] 【院刊】-【201408期】游戏扫拍卖行（排序算法之冒泡法） [复制链接]