浏览器排序对比-Chrome VS Firefox
作者：颜亦浠@毛豆前端
Chrome浏览器和Firefox浏览器对一些算法的实现存在差异，以前遇到过一个问题，做了一个记录，下面就和大家一起探讨下。
一、问题描述
接口返回数据相同，经过排序后，同一个页面两个浏览器展示效果不同。
二、问题定位
1、前端排序算法不对
2、其他因素影响
重新梳理后，发现sort用法写的不对。
sort()如果不带参数，就是按照字母顺序对数组中的元素进行排序，也就是按照字母编码的顺序进行排序。
如果sort()中传入排序规则函数，则可以自定义排序。
规则如下：
1、比较函数应该有两个参数a,b
2、 若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。若 a 等于 b，则返回 0。若 a 大于 b，则返回一个大于 0 的值。
修改之后在打断点验证的过程中发现，两个浏览器遍历过程中每一次的结果是不同的，虽然最终排序的结果一致。
深究发现，两个浏览器内核在进行排序是所采用的算法不同。
火狐sort排序用的是归并排序，chrome浏览器用的是插入排序、快速排序（数量小于10的数组使用 InsertionSort，比10大的数组则使用 QuickSort）
三、几种算法的基本实现以及对比
1、归并排序(Merge Sort)
基本思想：将两个有序数列合并成一个有序数列，包括从上往下、从下往上两种方式，区别在于分组大小，前者倾向于首先均分为两个组，后者倾向于分成每组只有一个元素的多个组。
基本demo：
// 归并排序的一般实现
const merge = (left, right) => {
const result = [];
while (left.length && right.length) {
if(left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift())
}
}
while(left.length) result.push(left.shift());
while(right.length) result.push(right.shift());
return result;
}
const mergeSort = arr => {
const len = arr.length;
if (len < 2) {
return arr;
}
let middle = Math.floor(len/2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right))
}
2、快速排序(Quick Sort)
基本思想：在数组中选择一个基数，比基数大的放在右边子数组，比基数小的放在左边子数组，然后在分别对左右两边的数组分别执行以上操作，直到所分成的数组都只有一个元素。
基本demo：
//快速排序的一般实现
const quickSort1 = arr => {
if (arr.length <= 1) {
return arr;
}
const midIndex = Math.floor(arr.length / 2);
const valArr = arr.splice(midIndex, 1);
const midIndexVal = valArr[0];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < midIndexVal) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
3、插入排序(Insertion Sort)
比较适用于大部分元素已经排序好的情况。
基本思想：把整个数组拆分成两个子数组，一个为按顺序排好的，一个为没有排序的，每次从没有排序的数组中拆除一个数，将起放入已经排序好的数组中并排好序，直到没有排序的数组为空为止。
基本demo:
//插入排序的一般实现
const insertionSort = (nums) => {
for (let i = 1; i < nums.length; ++i) {
let preIndex = i -1;
let temp = nums[i];
while (j >=0 && nums[preIndex] > temp) {
nums[preIndex+1] = nums[preIndex];
preIndex--;
}
nums[preIndex+1] = temp;
}
return nums;
}
四、性能分析
时间复杂度：
- 归并排序（O(nlogn)）
- 快速排序（O(nlogn)）
- 插入排序(O(n²))
稳定性：
- 归并排序（稳定）
- 快速排序（不稳定）
- 插入排序（稳定）
优化方案：
- 插入排序：借助二分查找的折半插入
const binarySearch = (arr, maxIndex, value) => { let min = 0; let max = maxIndex; while (min <= max) { const mid = Math.floor((min + max) / 2); if (arr[mid] <= value) { min = mid + 1; } else { max = mid - 1; } } return min; } const insertionSort2 = (arr) => { for (let i = 1, len = arr.length; i < len; i++) { const temp = arr[i]; const insertIndex = binarySearch(arr, i - 1, arr[i]); for (let preIndex = i - 1; preIndex >= insertIndex; preIndex--) { arr[preIndex + 1] = arr[preIndex]; } arr[insertIndex] = temp; } return arr; } - 归并排序：空间优化，用array.splice 取代 array.slice，减少空间消耗;对其中规模较小的子数组，使用插入排序；
- 快速排序：in-place
const swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};
const partition = (arr, left, right) => {
let pivot = left, //设定基准值（pivot）
index = pivot + 1;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
};
const quickSort = (arr, left, right) => {
let len = arr.length, index;
left = typeof left != 'number' ? 0 : left;
right = typeof right != 'number' ? len-1 : right;
if (left < right ) {
index = partition(arr, left, right);
quickSort(arr, left, index - 1);
quickSort(arr, index + 1, right);
}
return arr;
}