亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

itvincent / 1206人閱讀

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

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


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


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

ECMAScript 5.1

ECMAScript 6.0

ECMAScript 草案

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

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

表格內容部分來自于維基百科

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

V8 引擎的一段注釋

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

Google Chrome 對 sort 做了特殊處理，對于長度 <= 10 的數(shù)組使用的是插入排序(穩(wěn)定排序算法) ，>10 的數(shù)組使用的是快速排序?？焖倥判蚴遣环€(wěn)定的排序算法。

但是很明顯比我們常見的快速排序要復雜得多，不過核心算法還是快速排序。算法復雜的原因在于 v8 出于性能考慮進行了很多優(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);
}

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

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

各種算法的對比
排序類型 平均情況 最好情況 最壞情況 輔助空間 穩(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)定性取決于桶內排序的穩(wěn)定性, 因此其穩(wěn)定性不確定。

算法時間復雜度

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

常用的時間復雜度所耗費的時間從小到大依次是

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

圖片來源

算法的時間復雜度與運行時間有一些常見的比例關系 查看圖表來源

復雜度 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

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

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

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

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

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

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

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

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

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

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

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

舉個例子：

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

1、按價格進行倒排序；

2、相同價格則按照競標順位（即價格提交時間）進行正排序。

排序若是在前端進行，那么采用快速排序的瀏覽器中顯示的中標者很可能是不符合預期的。

解決辦法

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

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

工具

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

擴展閱讀

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

參考文檔

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

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

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/87289.html

相關文章

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

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

    姘擱『 評論0 收藏0

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

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

    Mr_zhang 評論0 收藏0

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

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

    Snailclimb 評論0 收藏0

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

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

    李昌杰 評論0 收藏0

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

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

    h9911 評論0 收藏0

發(fā)表評論

0條評論

itvincent

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<