資訊專欄INFORMATION COLUMN
摘要：通過看源代碼可以發(fā)現(xiàn)，的數(shù)組排序算法實現(xiàn)的也是快速排序。而且相比較于，它就只是實現(xiàn)了純粹的快速排序，完全沒有中的那些性能優(yōu)化的蹤影。
引言
幾個月前面試的時候被問過javascript中sort方法的具體算法實現(xiàn)，當(dāng)時回答的是要看下瀏覽器引擎的實現(xiàn)，今天看到了EFE關(guān)于前端排序的博客，正好學(xué)習(xí)下
問題描述我們經(jīng)常發(fā)現(xiàn)不同瀏覽器的排序結(jié)果不同，由于不同引擎在算法選擇上的差異，在瀏覽器中實際執(zhí)行的排序效果是不一致的
Chrome中的實現(xiàn)Chrome的JavaScript引擎是v8。由于它是開源的，所以可以直接看源代碼。
核心算法是快排，但是Chrome做了很多優(yōu)化，所以看上去很復(fù)雜,Chrome做的具體優(yōu)化可以看原博客,里面有比較詳細的介紹，身為前端覺得基礎(chǔ)知識不夠用所以沒有深入去看
Firefox中的實現(xiàn)按照現(xiàn)有的信息，SpiderMoney內(nèi)部實現(xiàn)了歸并排序。
Microsoft Edge中的實現(xiàn)Microsoft Edge的JavaScript引擎Chakra的核心部分代碼已經(jīng)于2016年初在Github開源。
通過看源代碼可以發(fā)現(xiàn)，Chakra的數(shù)組排序算法實現(xiàn)的也是快速排序。而且相比較于v8，它就只是實現(xiàn)了純粹的快速排序，完全沒有v8中的那些性能優(yōu)化的蹤影。
解決排序穩(wěn)定性的差異從目前已知的情況來看，所有主流瀏覽器（包括IE6，7，8）對于數(shù)組排序算法的實現(xiàn)基本可以枚舉：
歸并排序 / Timsort
快速排序
所以，我們將快速排序經(jīng)過定制改造，變成穩(wěn)定排序的是不是就可以了？
一般來說，針對對象數(shù)組使用不穩(wěn)定排序會影響結(jié)果。而其他類型數(shù)組本身使用穩(wěn)定排序或不穩(wěn)定排序的結(jié)果是相等的。
方案代碼示例
"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));
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/80320.html
摘要：寫在前面專題系列是我寫的第二個系列，第一個系列是深入系列。專題系列自月日發(fā)布第一篇文章，到月日發(fā)布最后一篇，感謝各位朋友的收藏點贊，鼓勵指正。 寫在前面 JavaScript 專題系列是我寫的第二個系列，第一個系列是 JavaScript 深入系列。 JavaScript 專題系列共計 20 篇，主要研究日常開發(fā)中一些功能點的實現(xiàn)，比如防抖、節(jié)流、去重、類型判斷、拷貝、最值、扁平、柯里...
摘要：源碼地址為了簡化篇幅，我們對這個數(shù)組進行分析，數(shù)組長度為，此時采用的是插入排序。插入排序的源碼是其原理在于將第一個元素視為有序序列，遍歷數(shù)組，將之后的元素依次插入這個構(gòu)建的有序序列中。 JavaScript 專題系列第十九篇，講解數(shù)組亂序，重點探究 Math.random() 為什么不能真正的亂序？ 亂序 亂序的意思就是將數(shù)組打亂。 嗯，沒有了，直接看代碼吧。 Math.random ...
摘要：理解的函數(shù)基礎(chǔ)要搞好深入淺出原型使用原型模型，雖然這經(jīng)常被當(dāng)作缺點提及，但是只要善于運用，其實基于原型的繼承模型比傳統(tǒng)的類繼承還要強大。中文指南基本操作指南二繼續(xù)熟悉的幾對方法，包括，，。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。 怎樣使用 this 因為本人屬于偽前端，因此文中只看懂了 8 成左右，希望能夠給大家?guī)韼椭?...（據(jù)說是阿里的前端妹子寫的） this 的值到底...
摘要：規(guī)范中定義了瀏覽器何時進行渲染更新，了解它有助于性能優(yōu)化。結(jié)合一些資料，對上邊規(guī)范給出一些理解有誤請指正每個線程都有自己的。列為，列為，列為。我們都知道是單線程，渲染計算和腳本運行共用同一線程網(wǎng)絡(luò)請求會有其他線程，導(dǎo)致腳本運行會阻塞渲染。 本文轉(zhuǎn)自blog 轉(zhuǎn)載請注明出處 異步的思考 event loops隱藏得比較深，很多人對它很陌生。但提起異步，相信每個人都知道。異步背后的靠山就是...
閱讀 2753·2023-04-25 20:28
閱讀 1949·2021-11-22 09:34
閱讀 3778·2021-09-26 10:20
閱讀 1947·2021-09-22 16:05
閱讀 3151·2021-09-09 09:32
閱讀 2602·2021-08-31 09:40
閱讀 2179·2019-08-30 13:56
閱讀 3382·2019-08-29 17:01
