温故知新之冒泡排序

游戏开始

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