归并排序

背景

• Array.prototype.sort的实现，不同浏览器有不同的算法实现
• chrome使用的快排
• Firefox使用的归并排序

---

归并排序

• 是一种稳定的排序算法O(nlogn)
• 核心原理
• 有效的排列两个有序数组
• [5,4,1,22]&&[12,32,45,21]

var tmp = [];
var left = [5,4,1,22];
var right = [12,32,45,21];
//对两个有序数组的第一个进行大小比较
//将小的推入tmp,并在原数组中删除
//这样的结果是在进行2*length比较之前就有一个数组长度为0，跳出比较
//tmp中存在的是有序的小值
//长度不为0的数组中还存在的是有序的大值
//将两者合并返回新的有序数组
while(left.length && right.length){
    if(left[0]<right[0]){
       tmp.push(left.shilf());
    } else {
       tmp.push(right.shift());
    }
}
return tmp.concat(left, right)

• 完整代码

  function merge(left, right) {
      var tmp = [];

      while (left.length && right.length) {
        if (left[0] < right[0])
          tmp.push(left.shift());
        else
          tmp.push(right.shift());
      }
      return tmp.concat(left, right);
  }

  function mergeSort(a) {
      if (a.length === 1) 
        return a;

      var mid = ~~(a.length / 2)
        , left = a.slice(0, mid)
        , right = a.slice(mid);

      return merge(mergeSort(left), mergeSort(right));
  }

• 核心原理的基础上加入递归思想

---

快速排序

• 是一种不稳定算法O(nlogn)-O(n2)
• http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html

---

稳定算法VS不稳定算法

• 什么是算法稳定性
• 两个相等的数，排序前排序后前后位置不变
• 稳定算法
• 冒泡排序
• 归并排序
• 不稳定算法
• 快速排序
• 选择排序
• 不稳定算法出现问题场景

   某市的机动车牌照拍卖系统，最终中标的规则为：

   1. 按价格进行倒排序；
   2. 相同价格则按照竞标顺位（即价格提交时间）进行正排序。
   排序若是在前端进行，那么采用快速排序的浏览器中显示的中标者很可能是不符合预期的