#高考加油#每一天的学习就是对自己的投资

javascript系列--深入浅出的理解javascript的快排sort实现原理

一、前言

之前在技术群中看到有人说,Array.prototype.sort方法会根据需要排序的数组的大小使用不同的排序算法,上次写了一篇排序算发,刚好赶上今天研究一下原生的sort,原生的sort已经见识到了排序快,时间复杂度O(nlogn)。


二、Array.prototype.sort到底使用什么排序算法

其实这个查了一下ECMAScript各个版本的实现代码,比如5.1版本,6.0版本等等

我们来看一下5.1版本是咋说的。

5.1地址:http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.4.11


6.0地址:http://www.ecma-international.org/ecma-262/6.0/#sec-array.prototype.sort

大致的意思就是说,sort排序算法不一定稳定,但是并没有说具体是使用什么样的排序算法实现的。

所以各个浏览器才给出了自己的实现方式,sort排序算法是由运行环境决定的。表格内容来源:维基百科

浏览器使用的 JavaScript 引擎排序算法源码地址
Google ChromeV8插入排序和快速排序sort 源码实现
Mozilla FirefoxSpiderMonkey归并排序sort 源码实现
SafariNitro(JavaScriptCore )归并排序和桶排序sort 源码实现
Microsoft Edge 和 IE(9+)Chakra快速排序sort 源码实现


1、源码分析

我们来看一下v8的QuickSort(快排)方法:

var QuickSort = 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 {
        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;
      }
    }
  };

v8的sort还是要比我们常见的快排算法复杂,不过核心算法还是快速排序,复杂的原因是v8对于性能的考虑进行了优化,比如如果递归很深的话,很容易出现“爆战”。每次我们分区后,v8引擎会选择元素少的分区进行递归,而将元素多的分区直接通过循环处理,无疑这样的处理大大减小了递归深度。这是一个很巧妙的实现。具体代码如下

 if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }



(1)v8源码的注释

// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.

v8引擎对sort函数做了处理,映射到ArraySort方法,然后调用InnerArraySort内部数组排序(注释的地方),对于length <= 22,数组使用的是插入排序InsertionSort(稳定的排序算法),减少递归深度,`>10`的数组使用快速排序QuickSort(不稳定的排序算法)。

PS:记得以前是对于数组长度<=10的数组用插入,>10使用快速排序。


(2)safari nitro引擎源码

sort方法映射到array_sort方法。然后调用了js_MergeSort方法。

默认的使用的桶排序(bucket sort),稳定的排序,如果sort传入的自定义函数作为参数,就使用归并排序(merge sort),稳定的排序。

火狐的sort核心排序主要还是归并排序。


(3)Microsoft Edge 和 IE(9+) 使用的不稳定排序算法 - 快速排序。

但是 IE(6、7、8)使用的稳定算法。


三、算法时间各个参数对比

排序类型平均情况最好情况最坏情况辅助空间稳定性
快速排序O(nlogn)O(nlogn)O(n²)O(nlogn)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定
插入排序O(n²)O(n)O(n²)O(1)稳定
桶排序O(n+k)O(n+k)O(n²)O(n+k)稳定

所耗费的时间从小到大依次:

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)

算法的时间复杂度与运行时间有一些常见的比例关系:

复杂度1020501001,00010,000100,000
O(1)< 1s< 1s< 1s< 1s< 1s< 1s< 1s
O(log(n))< 1s< 1s< 1s< 1s< 1s< 1s< 1s
O(n)< 1s< 1s< 1s< 1s< 1s< 1s< 1s
O(n*log(n))< 1s< 1s< 1s< 1s< 1s< 1s< 1s
O(n²)< 1s< 1s< 1s< 1s< 1s2 s3-4 min
O(n³)< 1s< 1s< 1s< 1s20 s5 hours231 days
O(2^n)< 1s< 1s260 dayshangshangshangshangs
O(n!)< 1shangshangshangshangshangshangs
O(n^n)3-4 minhangshangshangshangshangshangs

想看自己浏览器排序算法的稳定性? https://ofb.net/~sethml/is-sort-stable.html

我们先通过这个在线网站大体测试一下:http://math.hws.edu/eck/js/sorting/xSortLab.html


四、排序稳定性的理解

当相等的元素是无法分辨的,比如像是整数,稳定性并不是一个问题。

以他们的第一个数字来排序。比如:(4, 1) (3, 1) (3, 7)(5, 6)

在这个状况下,有可能产生两种不同的结果,一个是让相等键值的纪录维持相对的次序,而另外一个则没有:

(3, 1)  (3, 7)  (4, 1)  (5, 6)  (维持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)


五、不同浏览器实现的影响

不同浏览器实现的影响,实质就是排序算法不稳定有什么影响。

举个例子:

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

1、按价格进行倒排序;

2、相同价格则按照竞标顺位(即价格提交时间)进行正排序。

排序若是在前端进行,那么采用快速排序的浏览器中显示的中标者很可能是不符合预期的。

那怎么解决呢?就是自己写一个稳定的排序函数或者将排序扔给后端。以此保证浏览器的一致性。


六、参考

1、javascript系列--十大排序算法的总结(冒泡,选择,插入,希尔,归并,快排,堆排序,计数排序,桶排序,基数排序):https://www.mwcxs.top/page/734.html

https://hufangyun.com/2017/sort-array/

2、

聊聊前端排序的那些事:https://efe.baidu.com/blog/talk-about-sort-in-front-end/

3、JavaScript 排序算法汇总:http://www.qcyoung.com/2016/12/18/JavaScript%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%B1%87%E6%80%BB/

4、https://segmentfault.com/a/1190000008138236

5、https://hufangyun.com/2017/sort-array/

6、源码:https://github.com/v8/v8/blob/ad82a40509c5b5b4680d4299c8f08d6c6d31af3c/src/js/array.js


感谢你的阅读,本文由 sau交流学习社区 版权所有。
如若转载,请注明出处:sau交流学习社区-power by saucxs(程新松)(/page/745.html)
交流咨询
    官方QQ群
    群号663940201,欢迎加入!
    sau交流学习社区交流群

图文推荐

saucxs聊天机器人
saucxs
hi ,欢迎来到sau交流学习社区,欢迎与我聊天,问我问题哦!