javascript排序問(wèn)題探究

scola666 發(fā)布于2019-08-20 10:47 / 2070人閱讀

摘要：通過(guò)看源代碼可以發(fā)現(xiàn)，的數(shù)組排序算法實(shí)現(xiàn)的也是快速排序。而且相比較于，它就只是實(shí)現(xiàn)了純粹的快速排序，完全沒(méi)有中的那些性能優(yōu)化的蹤影。

引言

幾個(gè)月前面試的時(shí)候被問(wèn)過(guò)javascript中sort方法的具體算法實(shí)現(xiàn)，當(dāng)時(shí)回答的是要看下瀏覽器引擎的實(shí)現(xiàn)，今天看到了EFE關(guān)于前端排序的博客，正好學(xué)習(xí)下

問(wèn)題描述

我們經(jīng)常發(fā)現(xiàn)不同瀏覽器的排序結(jié)果不同，由于不同引擎在算法選擇上的差異，在瀏覽器中實(shí)際執(zhí)行的排序效果是不一致的

Chrome中的實(shí)現(xiàn)

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

核心算法是快排，但是Chrome做了很多優(yōu)化，所以看上去很復(fù)雜,Chrome做的具體優(yōu)化可以看原博客,里面有比較詳細(xì)的介紹，身為前端覺(jué)得基礎(chǔ)知識(shí)不夠用所以沒(méi)有深入去看

Firefox中的實(shí)現(xiàn)

按照現(xiàn)有的信息，SpiderMoney內(nèi)部實(shí)現(xiàn)了歸并排序。

Microsoft Edge中的實(shí)現(xiàn)

Microsoft Edge的JavaScript引擎Chakra的核心部分代碼已經(jīng)于2016年初在Github開(kāi)源。

通過(guò)看源代碼可以發(fā)現(xiàn)，Chakra的數(shù)組排序算法實(shí)現(xiàn)的也是快速排序。而且相比較于v8，它就只是實(shí)現(xiàn)了純粹的快速排序，完全沒(méi)有v8中的那些性能優(yōu)化的蹤影。

解決排序穩(wěn)定性的差異

從目前已知的情況來(lái)看，所有主流瀏覽器（包括IE6，7，8）對(duì)于數(shù)組排序算法的實(shí)現(xiàn)基本可以枚舉：

歸并排序 / Timsort

快速排序

所以，我們將快速排序經(jīng)過(guò)定制改造，變成穩(wěn)定排序的是不是就可以了？

一般來(lái)說(shuō)，針對(duì)對(duì)象數(shù)組使用不穩(wěn)定排序會(huì)影響結(jié)果。而其他類(lèi)型數(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));
}