javascript排序問題探究

scola666 發布于2019-08-20 10:47 / 2074人閱讀

摘要：通過看源代碼可以發現，的數組排序算法實現的也是快速排序。而且相比較于，它就只是實現了純粹的快速排序，完全沒有中的那些性能優化的蹤影。

引言

幾個月前面試的時候被問過javascript中sort方法的具體算法實現，當時回答的是要看下瀏覽器引擎的實現，今天看到了EFE關于前端排序的博客，正好學習下

問題描述

我們經常發現不同瀏覽器的排序結果不同，由于不同引擎在算法選擇上的差異，在瀏覽器中實際執行的排序效果是不一致的

Chrome中的實現

Chrome的JavaScript引擎是v8。由于它是開源的，所以可以直接看源代碼。

核心算法是快排，但是Chrome做了很多優化，所以看上去很復雜,Chrome做的具體優化可以看原博客,里面有比較詳細的介紹，身為前端覺得基礎知識不夠用所以沒有深入去看

Firefox中的實現

按照現有的信息，SpiderMoney內部實現了歸并排序。

Microsoft Edge中的實現

Microsoft Edge的JavaScript引擎Chakra的核心部分代碼已經于2016年初在Github開源。

通過看源代碼可以發現，Chakra的數組排序算法實現的也是快速排序。而且相比較于v8，它就只是實現了純粹的快速排序，完全沒有v8中的那些性能優化的蹤影。

解決排序穩定性的差異

從目前已知的情況來看，所有主流瀏覽器（包括IE6，7，8）對于數組排序算法的實現基本可以枚舉：

歸并排序 / Timsort

快速排序

所以，我們將快速排序經過定制改造，變成穩定排序的是不是就可以了？

一般來說，針對對象數組使用不穩定排序會影響結果。而其他類型數組本身使用穩定排序或不穩定排序的結果是相等的。

方案代碼示例

"use strict";

const INDEX = Symbol("index");

function getComparer(compare) {
    return function (left, right) {
        let result = compare(left, right);

        return result === 0 ? left[INDEX] - right[INDEX] : result;
    };
}

function sort(array, compare) {
    array = array.map(
        (item, index) => {
            if (typeof item === "object") {
                item[INDEX] = index;
            }

            return item;
        }
    );

    return array.sort(getComparer(compare));
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/80320.html

JavaScript專題系列20篇正式完結！

摘要：寫在前面專題系列是我寫的第二個系列，第一個系列是深入系列。專題系列自月日發布第一篇文章，到月日發布最后一篇，感謝各位朋友的收藏點贊，鼓勵指正。寫在前面 JavaScript 專題系列是我寫的第二個系列，第一個系列是 JavaScript 深入系列。 JavaScript 專題系列共計 20 篇，主要研究日常開發中一些功能點的實現，比如防抖、節流、去重、類型判斷、拷貝、最值、扁平、柯里...

sixleaves 2019-08-21 17:15 評論0 收藏0
JavaScript專題之亂序

摘要：源碼地址為了簡化篇幅，我們對這個數組進行分析，數組長度為，此時采用的是插入排序。插入排序的源碼是其原理在于將第一個元素視為有序序列，遍歷數組，將之后的元素依次插入這個構建的有序序列中。 JavaScript 專題系列第十九篇，講解數組亂序，重點探究 Math.random() 為什么不能真正的亂序？亂序亂序的意思就是將數組打亂。嗯，沒有了，直接看代碼吧。 Math.random ...

I_Am 2019-08-21 17:00 評論0 收藏0
JavaScript深入淺出

摘要：理解的函數基礎要搞好深入淺出原型使用原型模型，雖然這經常被當作缺點提及，但是只要善于運用，其實基于原型的繼承模型比傳統的類繼承還要強大。中文指南基本操作指南二繼續熟悉的幾對方法，包括，，。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。怎樣使用 this 因為本人屬于偽前端，因此文中只看懂了 8 成左右，希望能夠給大家帶來幫助....（據說是阿里的前端妹子寫的） this 的值到底...

blair 2019-08-21 18:26 評論0 收藏0
從event loop規范探究javaScript異步及瀏覽器更新渲染時機

摘要：規范中定義了瀏覽器何時進行渲染更新，了解它有助于性能優化。結合一些資料，對上邊規范給出一些理解有誤請指正每個線程都有自己的。列為，列為，列為。我們都知道是單線程，渲染計算和腳本運行共用同一線程網絡請求會有其他線程，導致腳本運行會阻塞渲染。本文轉自blog 轉載請注明出處異步的思考 event loops隱藏得比較深，很多人對它很陌生。但提起異步，相信每個人都知道。異步背后的靠山就是...

13651657101 2019-08-20 16:15 評論0 收藏0