作者:颜亦浠@毛豆前端

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;
    }

毛豆前端团队

never stop, always on the way!