背景
- 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));
}
快速排序
稳定算法VS不稳定算法
- 什么是算法稳定性
- 两个相等的数，排序前排序后前后位置不变
- 稳定算法
- 冒泡排序
- 归并排序
- 不稳定算法
- 快速排序
- 选择排序
- 不稳定算法出现问题场景
某市的机动车牌照拍卖系统，最终中标的规则为：
1. 按价格进行倒排序；
2. 相同价格则按照竞标顺位（即价格提交时间）进行正排序。
排序若是在前端进行，那么采用快速排序的浏览器中显示的中标者很可能是不符合预期的
