温故知新之冒泡排序

游戏开始

冒泡排序是大学里学的第一个算法,我记得当时老师做了一个游戏,任意挑选了一纵列同学全部站立,一共 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程序实现

//先把要比较的同学放入一个数组
function bubbleSoft(arrary){
//设置变量
var length = arrary.length,//一共 5 位同学参加比较
i = length-1,//共 5 个同学参与,比较了 4 轮
j,//数组下标,指代其中一个同学
temp;//交换的时候,临时存放下个子高的同学
for(i;i>0;i--){
for(j=0;j<i;j++){
//交换位置开始了
//如果第 j+1 个同学比第 j 个同学高,那么就执行换位措施
if(arrary[j+1] > arrary[j]){
temp = arrary[j+1];//把高个子先存在 temp 中
arrary[j+1] = arrary[j];//把小个子换到高个子位置上去
arrary[j] = temp;//把 temp 里的高个子换到小个子的位置上去
}
}
}
return arrary;
}

弊端:假设我们一开始,这一纵列同学本身就是从高到小的升高排列,那么我们的冒泡算法还是要跑 4 轮,才会给出结果,你说傻不傻?

标记域优化

如果我们第一轮比较,发现顺序没有变化,那就标记下,答案显而易见,根本不需要再比较了。

//先把要比较的同学放入一个数组
function bubbleSoft(arrary){
//设置变量
var length = arrary.length,//一共 5 位同学参加比较
i = length-1,//共 5 个同学参与,比较了 4 轮
j,//数组下标,指代其中一个同学
temp,//交换的时候,临时存放下个子高的同学
flag = true;//初始化标记为 true
for(i;i>0 && flag;i--){
flag = false;//进行一次,咱就标记为 false
for(j=0;j<i;j++){
//交换位置开始了
//如果第 j+1 个同学比第 j 个同学高,那么就执行换位措施
if(arrary[j+1] > arrary[j]){
temp = arrary[j+1];//把高个子先存在 temp 中
arrary[j+1] = arrary[j];//把小个子换到高个子位置上去
arrary[j] = temp;//把 temp 里的高个子换到小个子的位置上去
flag = true;//跑这里来了,说明有交换,再标记为 true,进行下一次循环
}
}
}
return arrary;
}
坚持原创技术分享,您的支持将鼓励我继续创作!