游戏开始
冒泡排序是大学里学的第一个算法,我记得当时老师做了一个游戏,任意挑选了一纵列同学全部站立,一共 5 个同学。
第一轮,我们从第 1 排的位置开始
- 先让第 1 排的同学跟第 2 排的同学比高低,两者较高的同学需要换到第 1 排来
- 然后第 2 排的同学跟第 3 排的同学比较,两者较高的同学需要换到第 2 排来
- 之后第 3 排的同学跟第 4 排的同学比较,两者较高的同学需要换到第 3 排来
- 最后第 4 排的同学跟第 5 排的同学比较,两者较高的同学需要换到第 4 排来 按如此规律进行了,第 1 轮比较,我们找到了最小的同学。
接着,我们又开始新的一轮比较,当然这一轮要排除第 5 排的同学,因为该同学在上又一轮已经被筛选出来了,是个子最小的同学。
第二轮, 我们从第 2 排的位置开始
- 先让第 2 排的同学跟第 3 排的同学比较,两者较高的同学需要换到第 2 排来
- 然后第 2 排的同学跟第 3 排的同学比较,两者较高的同学需要换到第 3 排来
- 之后第 3 排的同学跟第 4 排的同学比较,两者较高的同学需要换到第 4 排来
- 最后第 4 排的同学跟第 5 排的同学比较,两者较高的同学需要换到第 4 排来
按如此规律进行了,第 2 轮比较,我们找到了倒数第二的小个子同学。
如此循环比较到最后一轮,我们一共比较了 4 轮,就把这一纵列同学的升高,按从高到低来排列了。
几个关键词:相邻
、轮
、调换
。
以上游戏就是个普通冒泡算法。
JavaScript程序实现
//先把要比较的同学放入一个数组 |
弊端:假设我们一开始,这一纵列同学本身就是从高到小的升高排列,那么我们的冒泡算法还是要跑 4 轮,才会给出结果,你说傻不傻?
标记域优化
如果我们第一轮比较,发现顺序没有变化,那就标记下,答案显而易见,根本不需要再比较了。
//先把要比较的同学放入一个数组 |