超市风云之冒泡排序

被公司辞退的三流程序员小M开了个小超市，招募了6个好基友，分别是小酥、小锣、小包、小枣、小栗和小威。其中小酥是最矮的可爱吃货，小威是标准帅气的大高个。档案室记载了他们的身高如下：

6个好基友的身高档案

某天，小M看不惯这6个狼狈为奸的好基友，想把他们统一摆放到货架上，希望整齐划一地按身高从低到高排列，可偏偏这几个好基友闹成一团，排列得乱糟糟的。这可难不倒程序员出身的老板，于是老板首先想到用「冒泡排序」来排序，说干就干，老板进行了第一轮的冒泡。

初始状态

1. 老板比较了小锣和小枣的身高，发现小枣身高 > 小锣身高，不需要交换；
2. 老板又比较了小枣和小酥的身高，发现小酥身高 < 小枣身高，交换两者位置；
3. 接着比较小枣和小包的身高，发现小包身高 < 小枣身高，交换两者位置；
4. 又比较小枣和小威身高，发现小威身高 > 小枣身高， 不需要交换；
5. 老板再比较小威和小栗的身高，发现小栗身高 < 小威身高，交换两者位置。

第一轮冒泡

通过第一轮冒泡，小威排列到了他应处的位置，依次类推：

• 第二轮冒泡之后，小栗能够排列完成
• 第三轮冒泡之后，小枣能够排列完成
• 第四轮冒泡之后，小包能够排列完成
• 第五轮冒泡之后，小锣能够排列完成
• 第六轮冒泡之后，小酥能够排列完成

通过简易的冒泡排序之后，6个好基友整齐划一的排列在了货架上，但这个过程花费了小M大量的精力，小M反思了一下：

• 第二轮冒泡的时候小锣和小酥交换了位置之后，实际上已经完成排序了，但他依旧进行了后续第三到第六这4轮冒泡
• 在第二轮冒泡时，小威的位置已经在第一轮冒泡中确定了，但还是依旧遍历比较了小栗和小威的身高，属于多余的操作

根据反思，小M终于明白为什么之前的公司的前辈总说自己写的冒泡算法不合格了。在冒泡算法的迭代过程中，可以设置两个参数：

• isSorted：记录本轮冒泡是否有元素交换，如果没有，则不再继续冒泡，如此可以减少冒泡次数到第三轮
• lastChangeIndex：记录上一次冒泡最后交换元素的位置，作为下一次冒泡的边界，避免重复的检查。

function sort(arr) {
  let temp;
  let sortBorder = arr.length - 1,
       lastChangeIndex = 0;
  for(let i = 0; i < arr.length; i++) {
    let isSorted = true;                            // 判断上一次冒泡是否交换了元素
    for(let j = 0; j < sortBorder; j++) {
      if(arr[j] > arr[j+1]) {
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        isSorted = false;
        lastChangeIndex = j;                        // 记录最后交换了元素的位置
      }
    }
    sortBorder = lastChangeIndex;
    if(isSorted) {
      break;
    }
  }
  return arr;
}