成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

深入淺出 JavaScript 的 Array.prototype.sort 排序算法

itvincent / 1154人閱讀

摘要：快速排序是不穩(wěn)定的排序算法。瀏覽器的實(shí)現(xiàn)不同有什么影響排序算法不穩(wěn)定有什么影響舉個(gè)例子某市的機(jī)動(dòng)車牌照拍賣系統(tǒng)，最終中標(biāo)的規(guī)則為按價(jià)格進(jìn)行倒排序相同價(jià)格則按照競(jìng)標(biāo)順位即價(jià)格提交時(shí)間進(jìn)行正排序。

本文要解決的問題 
1、找出 Array.prototype.sort 使用的什么排序算法


2、用一種直觀的方式展示 Array.prototype.sort 的時(shí)間復(fù)雜度，看看它有多快？


3、實(shí)際開發(fā)中要注意的問題
Array.prototype.sort 各瀏覽器的算法實(shí)現(xiàn)

ECMAScript 5.1

ECMAScript 6.0

ECMAScript 草案

看完上面三個(gè)規(guī)范中 Array.prototype.sort 部分，我們會(huì)發(fā)現(xiàn) ECMAScript 不同版本規(guī)范對(duì) Array.prototype.sort 的定義中沒有要求用什么樣的排序方式實(shí)現(xiàn) sort() 方法，也沒有要求是否要采用穩(wěn)定排序算法（下文會(huì)解釋什么是穩(wěn)定排序算法）。

因此各瀏覽器都給出自己的實(shí)現(xiàn)方式：

表格內(nèi)容部分來(lái)自于維基百科

瀏覽器 使用的 JavaScript 引擎 排序算法 源碼地址
Google Chrome V8 插入排序和快速排序 sort 源碼實(shí)現(xiàn)
Mozilla Firefox SpiderMonkey 歸并排序 sort 源碼實(shí)現(xiàn)
Safari Nitro（JavaScriptCore ） 歸并排序和桶排序 sort 源碼實(shí)現(xiàn)
Microsoft Edge 和 IE(9+) Chakra 快速排序 sort 源碼實(shí)現(xiàn)
源碼分析

V8 引擎的一段注釋

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

Google Chrome 對(duì) sort 做了特殊處理，對(duì)于長(zhǎng)度 <= 10 的數(shù)組使用的是插入排序(穩(wěn)定排序算法) ，>10 的數(shù)組使用的是快速排序。快速排序是不穩(wěn)定的排序算法。

但是很明顯比我們常見的快速排序要復(fù)雜得多，不過核心算法還是快速排序。算法復(fù)雜的原因在于 v8 出于性能考慮進(jìn)行了很多優(yōu)化。

再看 safari Nitro 引擎的一段代碼

if (typeof comparator == "function")
  comparatorSort(array, length, comparator);
else if (comparator === null || comparator === @undefined)
  stringSort(array, length);

  省略....

function stringSort(array, length)
{
  var valueCount = compact(array, length);

  var strings = @newArrayWithSize(valueCount);
  for (var i = 0; i < valueCount; ++i)
      strings[i] = { string: @toString(array[i]), value: array[i] };

  bucketSort(array, 0, strings, 0);
}

  省略....

function comparatorSort(array, length, comparator)
{
  var valueCount = compact(array, length);
  mergeSort(array, valueCount, comparator);
}

默認(rèn)使用的桶排序，如果 sort 傳入的自定義函數(shù)作為參數(shù)，就是用歸并排序（穩(wěn)定排序算法）

Firefox 源碼就不貼了，上面的表格有源碼地址，使用的穩(wěn)定排序算法 — 歸并算法。
Microsoft Edge 和 IE(9+) 使用的不穩(wěn)定排序算法 - 快速排序。
但是 IE（6、7、8）使用的穩(wěn)定算法。

各種算法的對(duì)比
排序類型 平均情況 最好情況 最壞情況 輔助空間 穩(wěn)定性
快速排序 O(nlogn) O(nlogn) O(n2) O(nlogn) 不穩(wěn)定
歸并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 穩(wěn)定
插入排序 O(n2) O(n) O(n2) O(1) 穩(wěn)定
桶排序 O(n+k) O(n+k) O(n2) O(n+k) (不)穩(wěn)定

注: 桶排序的穩(wěn)定性取決于桶內(nèi)排序的穩(wěn)定性, 因此其穩(wěn)定性不確定。

算法時(shí)間復(fù)雜度

在進(jìn)行算法分析時(shí)，語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，
進(jìn)而分析T(n)隨著n的變化情況并確定T(n)的數(shù)量級(jí)。
算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間度量，記作：T(n)=O(f(n))。
它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，
稱作算法的時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。
其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。

常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2^n) < O(n!) < O(n^n)

圖片來(lái)源

算法的時(shí)間復(fù)雜度與運(yùn)行時(shí)間有一些常見的比例關(guān)系 查看圖表來(lái)源

復(fù)雜度 10 20 50 100 1,000 10,000 100,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(n2) < 1s < 1s < 1s < 1s < 1s 2 s 3-4 min
O(n3) < 1s < 1s < 1s < 1s 20 s 5 hours 231 days
O(2^n) < 1s < 1s 260 days hangs hangs hangs hangs
O(n!) < 1s hangs hangs hangs hangs hangs hangs
O(n^n) 3-4 min hangs hangs hangs hangs hangs hangs

維基百科關(guān)于算法穩(wěn)定性的解釋

當(dāng)相等的元素是無(wú)法分辨的，比如像是整數(shù)，穩(wěn)定性并不是一個(gè)問題。然而，假設(shè)以下的數(shù)對(duì)將要以他們的第一個(gè)數(shù)字來(lái)排序。
(4, 1)  (3, 1)  (3, 7)（5, 6）

在這個(gè)狀況下，有可能產(chǎn)生兩種不同的結(jié)果，一個(gè)是讓相等鍵值的紀(jì)錄維持相對(duì)的次序，而另外一個(gè)則沒有：

(3, 1)  (3, 7)  (4, 1)  (5, 6)  (維持次序）
(3, 7)  (3, 1)  (4, 1)  (5, 6) （次序被改變）

想看自己瀏覽器排序算法的穩(wěn)定性？ 點(diǎn)我

各種排序算法實(shí)現(xiàn)有多快？

我們先通過這個(gè)在線網(wǎng)站大體測(cè)試一下

對(duì)一個(gè)有 10000 個(gè)元素的數(shù)組，快速排序 > 歸并排序 >>> 插入排序
而且插入排序大于 1s 了。

對(duì)于一個(gè)只有 10 個(gè)元素的數(shù)組，插入排序 > 快速排序
這也說(shuō)明了為什么 chrome 在小于等于 10 個(gè)元素的小數(shù)組使用插入排序的原因了。

瀏覽器的實(shí)現(xiàn)不同有什么影響

排序算法不穩(wěn)定有什么影響

舉個(gè)例子：

某市的機(jī)動(dòng)車牌照拍賣系統(tǒng)，最終中標(biāo)的規(guī)則為：

1、按價(jià)格進(jìn)行倒排序；

2、相同價(jià)格則按照競(jìng)標(biāo)順位（即價(jià)格提交時(shí)間）進(jìn)行正排序。

排序若是在前端進(jìn)行，那么采用快速排序的瀏覽器中顯示的中標(biāo)者很可能是不符合預(yù)期的。

解決辦法

Array.prototype.sort 在不同瀏覽器中的差異和解決辦法

大體的思路就是，自己寫一個(gè)穩(wěn)定的排序函數(shù)，以保持各瀏覽器的一致性。

工具

1、在線排序算法對(duì)比網(wǎng)站
2、排序算法視覺圖

擴(kuò)展閱讀

1、快速排序（Quicksort）的Javascript實(shí)現(xiàn)
2、JS中可能用得到的全部的排序算法
3、7 種常用的排序算法-可視化
4、深入了解javascript的sort方法
5、JavaScript 排序算法匯總

參考文檔

聊聊前端排序的那些事
排序算法
JavaScript排序算法匯總

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/87289.html

相關(guān)文章

  • JS數(shù)據(jù)結(jié)構(gòu)與算法_排序和搜索算法

    摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法樹寫在前面這是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的最后一篇博客，也是在面試中常常會(huì)被問到的一部分內(nèi)容排序和搜索。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_樹 寫在前面 這是《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》的最后一篇博客，也是在面試中常常會(huì)被問到的一部分內(nèi)容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無(wú)心去深入研究排序相...

    姘擱『 評(píng)論0 收藏0

  • 【深度長(zhǎng)文】JavaScript數(shù)組所有API全解密

    摘要：關(guān)于我的博客掘金專欄路易斯專欄原文鏈接深度長(zhǎng)文數(shù)組全解密全文共字，系統(tǒng)講解了數(shù)組的各種特性和。構(gòu)造器構(gòu)造器用于創(chuàng)建一個(gè)新的數(shù)組。中聲明的數(shù)組，它的構(gòu)造函數(shù)是中的對(duì)象。 本文首發(fā)于CSDN網(wǎng)站，下面的版本又經(jīng)過進(jìn)一步的修訂。 關(guān)于 我的博客：louis blog 掘金專欄：路易斯專欄 原文鏈接：【深度長(zhǎng)文】JavaScript數(shù)組全解密 全文共13k+字，系統(tǒng)講解了JavaScrip...

    Mr_zhang 評(píng)論0 收藏0

  • JavaScript中的Array.prototype.sort方法詳解

    摘要：方法可以接受一個(gè)可選的參數(shù)，比較回調(diào)函數(shù)。方法會(huì)修改原本數(shù)組輸出如上，在調(diào)用方法后，自身數(shù)組被修改。對(duì)于長(zhǎng)數(shù)組會(huì)使用快速排序，而快速排序一般是不穩(wěn)定的。所以方法返回的數(shù)組永遠(yuǎn)是該方法認(rèn)為的升序數(shù)組。 前幾天在某公司面試的時(shí)候被問到關(guān)于這個(gè)方法的默認(rèn)值的問題（然而面試官跟我說(shuō)的其實(shí)是錯(cuò)的，當(dāng)場(chǎng)我還不夠底氣去反駁）。突然發(fā)現(xiàn)對(duì)這個(gè)方法的了解還不夠，因此回來(lái)查了資料，看了v8引擎的實(shí)現(xiàn)和EC...

    Snailclimb 評(píng)論0 收藏0

  • 【JS必知必會(huì)】高階函數(shù)詳解與實(shí)戰(zhàn)

    摘要：函數(shù)作為參數(shù)情況，，和是中內(nèi)置的高階函數(shù)。知道了到底啊什么是高階函數(shù)，有哪些類型的高階函數(shù)。公眾號(hào)技術(shù)棧路線大家好，我是，公眾號(hào)程序員成長(zhǎng)指北作者，這篇文章是必知必會(huì)系列的高階函數(shù)講解。 前言 一道經(jīng)典面試題： //JS實(shí)現(xiàn)一個(gè)無(wú)限累加的add函數(shù) add(1) //1 add(1)(2) //3 add(1)(2)(3) //6 當(dāng)大家看到這個(gè)面試題的時(shí)候，能否在第一時(shí)間想到...

    李昌杰 評(píng)論0 收藏0

  • JavaScript 排序算法圖解（JavaScript sorting algorithms）

    摘要：基礎(chǔ)構(gòu)造函數(shù)以下幾種排序算法做為方法放在構(gòu)造函數(shù)里。代碼圖解選擇排序選擇排序算法是一種原址比較排序算法。它的性能通常比其他的復(fù)雜度為的排序算法要好。代碼劃分過程圖解排序沒有定義用哪個(gè)排序算法，所以瀏覽器廠商可以自行去實(shí)現(xiàn)算法。 基礎(chǔ)構(gòu)造函數(shù) 以下幾種排序算法做為方法放在構(gòu)造函數(shù)里。 function ArrayList () { var array = []; // 交換位置...

    h9911 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<