Array.sort()相关

来源:http://www.chinese-glasses.com 作者:Web前端 人气:77 发布时间:2020-04-15
摘要:时间: 2019-09-26阅读: 158标签: 源码前言 问题描述 用Array.sort()在不传入自定义比较函数的情况下,排序结果是按位比较的结果,而不是预期的按数字大小排列的结果 var a = [1,2,11].sort()//a

时间: 2019-09-26阅读: 158标签: 源码前言

问题描述

用Array.sort()在不传入自定义比较函数的情况下,排序结果是按位比较的结果,而不是预期的按数字大小排列的结果

var a = [1,2,11].sort()
//a = [1, 11, 2]

今天有个小伙伴( chrome v59 )遇到一个这样的问题,

问题原因

The sort() method sorts the elements of an array in place and returns the array. The sort is not necessarily stable. The default sort order is according to string Unicode code points.
arr.sort([compareFunction]) compareFunction Optional. Specifies a function that defines the sort order. If omitted, the array is sorted according to each character's Unicode code point value, according to the string conversion of each element.

sort方法如果不提供compareFunction比较函数,那么就把数组中的元素转成字符串后按字符的Unicode码点进行比较。

[1,2,13,14,5,6,17,18,9,10,11,12,31,41].sort(()=0)// [18,1,13,14,5,6,17,2,9,10,11,12,31,41][1,2,13,14,5,6,17,18,9,10].sort(()=0)// [1,2,13,14,5,6,17,18,9,10]

More

于是,去翻了v8的源码,发现果不其然,另外还发现,v8的数组排序用了两个算法:
当需排序的数组长度<=10时,使用插入排序;
当需排序的数组长度>10时,使用快速排序。

然后我在自己电脑上( chrome v76 )测试是这样的结果

插入排序:

插入排序是将一个记录插入到已经排好序的数组中,从而获得一个新的排好序的、数组长度加1的有序列表。

  • step1: 从第一个元素开始,该元素可认为已被排完序;
  • step2: 取出下一个元素(a),并从已排完的有序数列中从前向后扫描(b);
  • step3: 若遍历到的已排序数列的当前元素(b)大于有序数列的下个元素(a),则将b向后移动一位;
  • step4: 重复step3,直至a>=b;
  • step5:将新元素a放置到b元素后;
  • step6: 重复step2-step5;

算法分析:

  • 最佳情况:输入数组按升序排列, T(n) = O(n)
  • 最差情况:输入数组按降序排列, T(n) = O(n2)
  • 平均情况:T(n) = O(n2)
function insertSort(arr){
  var len = arr.length
  for(var i = 1; i < length; i++){
    var element = arr[i];
    for(var j = i - 1; j >= 0; j--){
      var temp = arr[j]
      var isGreater = temp > element
      if(isGreater){
        arr[ j+1 ] = temp
      }else{
        break
      }
    }
    arr[ j+1 ] = element
  }
  return arr
}
[1,2,13,14,5,6,17,18,9,10,11,12,31,41].sort(()=0)// [1,2,13,14,5,6,17,18,9,10,11,12,31,41][1,2,13,14,5,6,17,18,9,10].sort(()=0)// [1,2,13,14,5,6,17,18,9,10]
快速排序:
  • step1: 在数据集中,选择一个元素作为'基准'(pivot );
  • step2: 所有小于pivot元素都移至pivot左侧,所有大于pivot元素都移至pivot右侧;
  • step3: 对pivot左右两侧子集都不断重复step1、step2,直至子集只剩一个元素为止。

我们知道,给一个 sort 的比较函数中返回0,表示当前比较的两个元素相等

附录

10bet,v8数组排序相关代码:

function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 10) arrays, insertion sort is used for efficiency.

  if (!IS_CALLABLE(comparefn)) {
    comparefn = function (x, y) {
      if (x === y) return 0;
      if (%_IsSmi(x) && %_IsSmi(y)) {
        return %SmiLexicographicCompare(x, y);
      }
      x = TO_STRING(x);
      y = TO_STRING(y);
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
  }
  function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
        var order = comparefn(tmp, element);
        if (order > 0) {
          a[j + 1] = tmp;
        } else {
          break;
        }
      }
      a[j + 1] = element;
    }
  };

  function GetThirdIndex(a, from, to) {
    var t_array = new InternalArray();
    // Use both 'from' and 'to' to determine the pivot candidates.
    var increment = 200 + ((to - from) & 15);
    var j = 0;
    from += 1;
    to -= 1;
    for (var i = from; i < to; i += increment) {
      t_array[j] = [i, a[i]];
      j++;
    }
    t_array.sort(function(a, b) {
      return comparefn(a[1], b[1]);
    });
    var third_index = t_array[t_array.length >> 1][0];
    return third_index;
  }

  function QuickSort(a, from, to) {
    var third_index = 0;
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
      }
      if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
      } else {
        // >> 右移运算符; value >> num 表明将value向右移动num位; value >> 1 = value / 2
        third_index = from + ((to - from) >> 1);
      }
      // Find a pivot as the median of first, last and middle element.
      var v0 = a[from];
      var v1 = a[to - 1];
      var v2 = a[third_index];
      var c01 = comparefn(v0, v1);
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1.
      var c02 = comparefn(v0, v2);
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
        var c12 = comparefn(v1, v2);
        if (c12 > 0) {
          // v0 <= v2 < v1
          var tmp = v1;
          v1 = v2;
          v2 = tmp;
        }
      }
      // v0 <= v1 <= v2
      a[from] = v0;
      a[to - 1] = v2;
      var pivot = v1;
      var low_end = from + 1;   // Upper bound of elements lower than pivot.
      var high_start = to - 1;  // Lower bound of elements greater than pivot.
      a[third_index] = a[low_end];
      a[low_end] = pivot;

      // From low_end to i are elements equal to pivot.
      // From i to high_start are elements that haven't been compared yet.
      partition: for (var i = low_end + 1; i < high_start; i++) {
        var element = a[i];
        var order = comparefn(element, pivot);
        if (order < 0) {
          a[i] = a[low_end];
          a[low_end] = element;
          low_end++;
        } else if (order > 0) {
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = comparefn(top_elem, pivot);
          } while (order > 0);
          a[i] = a[high_start];
          a[high_start] = element;
          if (order < 0) {
            element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
          }
        }
      }
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
    }
  };

  // Copy elements in the range 0..length from obj's prototype chain
  // to obj itself, if obj has holes. Return one more than the maximal index
  // of a prototype property.
  function CopyFromPrototype(obj, length) {
    var max = 0;
    for (var proto = %object_get_prototype_of(obj); proto;
         proto = %object_get_prototype_of(proto)) {
      var indices = IS_PROXY(proto) ? length : %GetArrayKeys(proto, length);
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = 0; i < proto_length; i++) {
          if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
            obj[i] = proto[i];
            if (i >= max) { max = i + 1; }
          }
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
          if (!HAS_OWN_PROPERTY(obj, index) && HAS_OWN_PROPERTY(proto, index)) {
            obj[index] = proto[index];
            if (index >= max) { max = index + 1; }
          }
        }
      }
    }
    return max;
  };

  // Set a value of "undefined" on all indices in the range from..to
  // where a prototype of obj has an element. I.e., shadow all prototype
  // elements in that range.
  function ShadowPrototypeElements(obj, from, to) {
    for (var proto = %object_get_prototype_of(obj); proto;
         proto = %object_get_prototype_of(proto)) {
      var indices = IS_PROXY(proto) ? to : %GetArrayKeys(proto, to);
      if (IS_NUMBER(indices)) {
        // It's an interval.
        var proto_length = indices;
        for (var i = from; i < proto_length; i++) {
          if (HAS_OWN_PROPERTY(proto, i)) {
            obj[i] = UNDEFINED;
          }
        }
      } else {
        for (var i = 0; i < indices.length; i++) {
          var index = indices[i];
          if (from <= index && HAS_OWN_PROPERTY(proto, index)) {
            obj[index] = UNDEFINED;
          }
        }
      }
    }
  };

  function SafeRemoveArrayHoles(obj) {
    // Copy defined elements from the end to fill in all holes and undefineds
    // in the beginning of the array.  Write undefineds and holes at the end
    // after loop is finished.
    var first_undefined = 0;
    var last_defined = length - 1;
    var num_holes = 0;
    while (first_undefined < last_defined) {
      // Find first undefined element.
      while (first_undefined < last_defined &&
             !IS_UNDEFINED(obj[first_undefined])) {
        first_undefined++;
      }
      // Maintain the invariant num_holes = the number of holes in the original
      // array with indices <= first_undefined or > last_defined.
      if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
        num_holes++;
      }

      // Find last defined element.
      while (first_undefined < last_defined &&
             IS_UNDEFINED(obj[last_defined])) {
        if (!HAS_OWN_PROPERTY(obj, last_defined)) {
          num_holes++;
        }
        last_defined--;
      }
      if (first_undefined < last_defined) {
        // Fill in hole or undefined.
        obj[first_undefined] = obj[last_defined];
        obj[last_defined] = UNDEFINED;
      }
    }
    // If there were any undefineds in the entire array, first_undefined
    // points to one past the last defined element.  Make this true if
    // there were no undefineds, as well, so that first_undefined == number
    // of defined elements.
    if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
    // Fill in the undefineds and the holes.  There may be a hole where
    // an undefined should be and vice versa.
    var i;
    for (i = first_undefined; i < length - num_holes; i++) {
      obj[i] = UNDEFINED;
    }
    for (i = length - num_holes; i < length; i++) {
      // For compatibility with Webkit, do not expose elements in the prototype.
      if (i in %object_get_prototype_of(obj)) {
        obj[i] = UNDEFINED;
      } else {
        delete obj[i];
      }
    }

    // Return the number of defined elements.
    return first_undefined;
  };

  if (length < 2) return array;

  var is_array = IS_ARRAY(array);
  var max_prototype_element;
  if (!is_array) {
    // For compatibility with JSC, we also sort elements inherited from
    // the prototype chain on non-Array objects.
    // We do this by copying them to this object and sorting only
    // own elements. This is not very efficient, but sorting with
    // inherited elements happens very, very rarely, if at all.
    // The specification allows "implementation dependent" behavior
    // if an element on the prototype chain has an element that
    // might interact with sorting.
    max_prototype_element = CopyFromPrototype(array, length);
  }

  // %RemoveArrayHoles returns -1 if fast removal is not supported.
  var num_non_undefined = %RemoveArrayHoles(array, length);

  if (num_non_undefined == -1) {
    // There were indexed accessors in the array.
    // Move array holes and undefineds to the end using a Javascript function
    // that is safe in the presence of accessors.
    num_non_undefined = SafeRemoveArrayHoles(array);
  }

  QuickSort(array, 0, num_non_undefined);

  if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
    // For compatibility with JSC, we shadow any elements in the prototype
    // chain that has become exposed by sort moving a hole to its position.
    ShadowPrototypeElements(array, num_non_undefined, max_prototype_element);
  }

  return array;
}

照理说,sort(()=0)后数组的元素顺序是不变的,和我的测试效果一致,

那为什么在 低版本的 chrome 上,不同长度的数组运用sort(()=0)后效果不一样呢?

定义

arr.sort([compareFunction])

这里我们引用MDN的一段话:

如果 compareFunction(a, b) 小于 0 ,那么 a 会被排列到 b 之前;

如果 compareFunction(a, b) 大于 0 , b 会被排列到 a 之前。

如果 compareFunction(a, b) 等于 0 , a 和 b 的相对位置不变。备注:ECMAScript 标准并不保证这一行为,而且也不是所有浏览器都会遵守(例如 Mozilla 在 2003 年之前的版本)

也就是说,有些浏览器不遵循compareFunction(a, b) 等于 0时, a 和 b 的相对位置不变的规则

这里我们看出来了,chrome v59 就是不遵循该规则的。 但是 数组长度较小时好像又遵循了?

这里我们猜测不同长度的数组会运用不同的排序算法

在分析源码之前,我们先简单提下,什么是 插入排序 和 快速排序

排序算法

我们假设比较函数为

comparefn = (a,b)= a-b
  1. 插入排序

遍历数组,将每个待排序元素插入到前面已排序的适当位置

插入排序分为 直接插入排序、二分查找插入排序、希尔排序

由于v8也只是用了直接插入排序,这里我们只实现它,其他几种不进行讨论,想要了解的可以参考这里,

function InsertionSort(array) { for (let i = 1; i  array.legnth; i++) { let element = array[i]; // 将待排序元素element插入对应位置 for (let j = i - 1; j = 0; j--) { let tmp = array[j]; // comparefn  0 表示element要排在tmp之前 if (comparefn(tmp, element)  0) { a[j + 1] = tmp; } else { // break; } } a[j + 1] = element; }};
  1. 快速排序

设定一个基准,利用该基准值大小将数组分为左右两部分

此时左右两部分可以独立排序,分别对左右两部分进行上面的操作

递归处理,直至数组排序完成

考虑到空间消耗,现在的快速排序一般都是指原地算法的快速排序

关于原地算法,参看-place_algorithm

下面有两者实现,基准值取左边的或者右边,效果差不多

function qsort(array){ function swap(arr,i1,i2){ let tmp = arr[i1] arr[i1] = arr[i2] arr[i2] = tmp } function partition(arr, left, right){ let storeIndex = left let pivot = arr[right] //基准 for(let i=left;iright;i++){ if(arr[i]pivot){ swap(arr,storeIndex++,i) } } swap(arr,storeIndex,right) return storeIndex } // 基准在左边 // function partition(arr, left, right){ // let storeIndex = left // let pivot = arr[left] //基准 // for(let i = left+1;i=right;i++){ // if(arr[i]pivot){ // swap(arr,++storeIndex,i) // } // } // swap(arr,storeIndex,left) // return storeIndex // } function sort(arr,left,right){ if(leftright){ let storeIndex = partition(arr, left, right); sort(arr, left, storeIndex - 1); sort(arr, storeIndex + 1, right); } } sort(array, 0, array.length - 1); return array}

v8 源码分析

理解了基本的排序算法,接下来我们开始研究源码。

比较 chrome v59 和 chrome v76 的 v8 实现差异在哪

如何查找对应chrome版本的 v8 源码

打开chrome://version/

上面显示的 JavaScript 即是 v8 的版本

Google Chrome 76.0.3809.132 (正式版本) (64 位) (cohort: Stable)操作系统 Windows 10 OS Version 1809 (Build 17763.316)JavaScript V8 7.6.303.29

也正如V8’s version numbering scheme所述

Chromium 76对应 v8 的7.6

接着我们直接去v8查看源码,这里主要看两个版本的

5.9.221

对应的排序算法源码地址

结合测试用例看更佳/test/mjsunit/array-sort

可以看出来,早期v8 排序的实现逻辑是用js写的,对应的实现为 ArraySort

utils.InstallFunctions(GlobalArray.prototype, DONT_ENUM, [ ... "sort", getFunction("sort", ArraySort), ...])

ArraySort

没有什么有用代码,直接进入 InnerArraySort

function ArraySort(comparefn) { CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort"); var array = TO_OBJECT(this); var length = TO_LENGTH(array.length); return InnerArraySort(array, length, comparefn);}

InnerArraySort

本文由10bet发布于Web前端,转载请注明出处:Array.sort()相关

关键词:

上一篇:网站很久没有收录该怎么办10bet?

下一篇:没有了

最火资讯