JavaScript中關於 v8 排序原始碼的問題

JavaScript 專題系列第二十篇，也是最後一篇，解讀v8 排序原始碼

前言

v8 是Chrome 的JavaScript 引擎，其中關於陣列的排序完全採用了JavaScript 實作。

排序所採用的演算法跟數組的長度有關，當數組長度小於等於 10 時，採用插入排序，大於 10 的時候，採用快速排序。 (當然了，這種說法並不嚴謹)。

我們先來看看插入排序和快速排序。

插入排序

原理

將第一個元素視為有序序列，遍歷數組，將之後的元素依次插入這個構建的有序序列中。

圖示

實作

function insertionSort(arr) {
    for (var i = 1; i < arr.length; i++) {
        var element = arr[i];
        for (var j = i - 1; j >= 0; j--) {
            var tmp = arr[j];
            var order = tmp - element;
            if (order > 0) {
                arr[j + 1] = tmp;
            } else {
                break;
            }
        }
        arr[j + 1] = element;
    }
    return arr;
}

var arr = [6, 5, 4, 3, 2, 1];
console.log(insertionSort(arr));

時間複雜度

時間複雜度是指執行演算法所需的計算工作量，它考察當輸入值大小趨近無窮時的情況，一般情況下，演算法中基本操作重複執行的次數是問題規模n 的某個函數。

最好情況：陣列升序排列，時間複雜度為：O(n)

最壞情況：陣列降序排列，時間複雜度為：O(n²)

穩定性

穩定性，是指相同的元素在排序後是否仍保持相對的位置。

要注意的是對於不穩定的排序演算法，只要舉出一個實例，即可說明它的不穩定性；而對於穩定的排序演算法，必須對演算法進行分析從而得到穩定的特性。

例如 [3, 3, 1]，排序後，還是 [3, 3, 1]，但其實是第二個 3 在 第一個 3 前，那這就是不穩定的排序演算法。

插入排序是穩定的演算法。

優勢

當陣列是快要排序好的狀態或是問題規模比較小的時候，插入排序效率更高。這也是為什麼 v8 會在陣列長度小於等於 10 的時候採用插入排序。

快速排序

原則

1. 選擇一個元素作為"基準"

2. 小於"基準"的元素，都移到"基準"的左邊；大於"基準"的元素，都移到"基準"的右邊。

3. 對"基準"左邊和右邊的兩個子集，不斷重複第一步和第二步，直到所有子集只剩下一個元素為止。

範例

範例和下面的實作方式來自阮一峰老師的《快速排序（Quicksort）的Javascript實作》

以陣列[ 85, 24, 63, 45, 17, 31, 96, 50] 為例：

第一步，選擇中間的元素45 作為"基準"。 （基準值可以任意選擇，但是選擇中間的值比較容易理解。）

第二步，依照順序，將每個元素與"基準"進行比較，形成兩個子集，一個"小於45"，另一個"大於等於45"。

第三步，對兩個子集不斷重複第一步和第二步，直到所有子集只剩下一個元素為止。

實作

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
    // 取数组的中间元素作为基准
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];

　　var left = [];
　　var right = [];

　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

然而這種實作方式需要額外的空間用來儲存左右子集，所以還有一種原地(in-place)排序的實作方式。

圖示

我們來看看原地排序的實作圖示：

為了讓大家看明白快速排序的原理，我調慢了執行速度。

在這張示意圖裡，基準的值規則是取最左邊的元素，黃色代表目前的基準，綠色代表小於基準的元素，紫色代表大於基準的元素。

我們會發現，綠色的元素會緊挨在基準的右邊，紫色的元素會被移到後面，然後交換基準和綠色的最後一個元素，此時，基準處於正確的位置，即前面的元素都小於基準值，後面的元素都大於基準值。然後再對前面的和後面的多個元素取基準，做排序。

in-place 實作

function quickSort(arr) {
    // 交换元素
    function swap(arr, a, b) {
        var temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    function partition(arr, left, right) {
        var pivot = arr[left];
        var storeIndex = left;

        for (var i = left + 1; i <= right; i++) {
            if (arr[i] < pivot) {
                swap(arr, ++storeIndex, i);
            }
        }

        swap(arr, left, storeIndex);

        return storeIndex;
    }

    function sort(arr, left, right) {
        if (left < right) {
            var storeIndex = partition(arr, left, right);
            sort(arr, left, storeIndex - 1);
            sort(arr, storeIndex + 1, right);
        }
    }

    sort(arr, 0, arr.length - 1);

    return arr;
}

console.log(quickSort(6, 7, 3, 4, 1, 5, 9, 2, 8))

穩定性

快速排序是不穩定的排序。如果要證明一個排序是不穩定的，你只用舉出一個實例就行。

所以我們舉一個唄~

就以数组 [1, 2, 3, 3, 4, 5] 为例，因为基准的选择不确定，假如选定了第三个元素(也就是第一个 3) 为基准，所有小于 3 的元素在前面，大于等于 3 的在后面，排序的结果没有问题。可是如果选择了第四个元素(也就是第二个 3 )，小于 3 的在基准前面，大于等于 3 的在基准后面，第一个 3 就会被移动到 第二个 3 后面，所以快速排序是不稳定的排序。

时间复杂度

阮一峰老师的实现中，基准取的是中间元素，而原地排序中基准取最左边的元素。快速排序的关键点就在于基准的选择，选取不同的基准时，会有不同性能表现。

快速排序的时间复杂度最好为 O(nlogn)，可是为什么是 nlogn 呢？来一个并不严谨的证明：

在最佳情况下，每一次都平分整个数组。假设数组有 n 个元素，其递归的深度就为 log₂n + 1，时间复杂度为 O(n)[(log₂n + 1)]，因为时间复杂度考察当输入值大小趋近无穷时的情况，所以会忽略低阶项，时间复杂度为：o(nlog₂n)。

如果一个程序的运行时间是对数级的，则随着 n 的增大程序会渐渐慢下来。如果底数是 10，lg1000 等于 3，如果 n 为 1000000，lgn 等于 6，仅为之前的两倍。如果底数为 2，log₂1000 的值约为 10，log₂1000000 的值约为 19，约为之前的两倍。我们可以发现任意底数的一个对数函数其实都相差一个常数倍而已。所以我们认为 O(logn)已经可以表达所有底数的对数了，所以时间复杂度最后为： O(nlogn)。

而在最差情况下，如果对一个已经排序好的数组，每次选择基准元素时总是选择第一个元素或者最后一个元素，那么每次都会有一个子集是空的，递归的层数将达到 n，最后导致算法的时间复杂度退化为 O(n²)。

这也充分说明了一个基准的选择是多么的重要，而 v8 为了提高性能，就对基准的选择做了很多优化。

v8 基准选择

v8 选择基准的原理是从头和尾之外再选择一个元素，然后三个值排序取中间值。

当数组长度大于 10 但是小于 1000 的时候，取中间位置的元素，实现代码为：

// 基准的下标
// >> 1 相当于除以 2 (忽略余数)
third_index = from + ((to - from) >> 1);

当数组长度大于 1000 的时候，每隔 200 ~ 215 个元素取一个值，然后将这些值进行排序，取中间值的下标，实现的代码为：

// 简单处理过
function GetThirdIndex(a, from, to) {
    var t_array = new Array();

    // & 位运算符
    var increment = 200 + ((to - from) & 15);

    var j = 0;
    from += 1;
    to -= 1;

    for (var i = from; i < to; i += increment) {
        t_array[j] = [i, a[i]];
        j++;
    }
    // 对随机挑选的这些值进行排序
    t_array.sort(function(a, b) {
        return comparefn(a[1], b[1]);
    });
    // 取中间值的下标
    var third_index = t_array[t_array.length >> 1][0];
    return third_index;
}

也许你会好奇 200 + ((to - from) & 15) 是什么意思？

& 表示是按位与，对整数操作数逐位执行布尔与操作。只有两个操作数中相对应的位都是 1，结果中的这一位才是 1。

以 15 & 127 为例：

15 二进制为： （0000 1111）

127 二进制为：（1111 1111）

按位与结果为：（0000 1111）＝ 15

所以 15 & 127 的结果为 15。

注意 15 的二进制为： 1111，这就意味着任何和 15 按位与的结果都会小于或者等于 15，这才实现了每隔 200 ~ 215 个元素取一个值。

v8 源码

终于到了看源码的时刻！源码地址为：https://github.com/v8/v8/blob/master/src/js/array.js#L758。

function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
        var element = a[i];
        for (var j = i - 1; j >= from; j--) {
            var tmp = a[j];
            var order = comparefn(tmp, element);
            if (order > 0) {
                a[j + 1] = tmp;
            } else {
                break;
            }
        }
        a[j + 1] = element;
    }
};


function QuickSort(a, from, to) {

    var third_index = 0;
    while (true) {
            // Insertion sort is faster for short arrays.
        if (to - from <= 10) {
            InsertionSort(a, from, to);
            return;
        }
        if (to - from > 1000) {
            third_index = GetThirdIndex(a, from, to);
        } else {
            third_index = from + ((to - from) >> 1);
        }
        // Find a pivot as the median of first, last and middle element.
        var v0 = a[from];
        var v1 = a[to - 1];
        var v2 = a[third_index];

        var c01 = comparefn(v0, v1);
        if (c01 > 0) {
            // v1 < v0, so swap them.
            var tmp = v0;
            v0 = v1;
            v1 = tmp;
        } // v0 <= v1.
        var c02 = comparefn(v0, v2);
        if (c02 >= 0) {
            // v2 <= v0 <= v1.
            var tmp = v0;
            v0 = v2;
            v2 = v1;
            v1 = tmp;
        } else {
            // v0 <= v1 && v0 < v2
            var c12 = comparefn(v1, v2);
            if (c12 > 0) {
                // v0 <= v2 < v1
                var tmp = v1;
                v1 = v2;
                v2 = tmp;
            }
        }

        // v0 <= v1 <= v2
        a[from] = v0;
        a[to - 1] = v2;

        var pivot = v1;

        var low_end = from + 1; // Upper bound of elements lower than pivot.
        var high_start = to - 1; // Lower bound of elements greater than pivot.

        a[third_index] = a[low_end];
        a[low_end] = pivot;

        // From low_end to i are elements equal to pivot.
        // From i to high_start are elements that haven't been compared yet.

        partition: for (var i = low_end + 1; i < high_start; i++) {
            var element = a[i];
            var order = comparefn(element, pivot);
            if (order < 0) {
                a[i] = a[low_end];
                a[low_end] = element;
                low_end++;
            } else if (order > 0) {
                do {
                    high_start--;
                    if (high_start == i) break partition;
                    var top_elem = a[high_start];
                    order = comparefn(top_elem, pivot);
                } while (order > 0);

                a[i] = a[high_start];
                a[high_start] = element;
                if (order < 0) {
                    element = a[i];
                    a[i] = a[low_end];
                    a[low_end] = element;
                    low_end++;
                }
            }
        }


        if (to - high_start < low_end - from) {
            QuickSort(a, high_start, to);
            to = low_end;
        } else {
            QuickSort(a, from, low_end);
            from = high_start;
        }
    }
}

var arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];

function comparefn(a, b) {
    return a - b
}

QuickSort(arr, 0, arr.length)
console.log(arr)

我们以数组 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 为例，分析执行的过程。

1.执行 QuickSort 函数 参数 from 值为 0，参数 to 的值 11。

2.10 < to - from < 1000 第三个基准元素的下标为 (0 + 11 >> 1) = 5，基准值 a[5] 为 5。

3.比较 a[0] a[10] a[5] 的值，然后根据比较结果修改数组，数组此时为 [0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10]

4.将基准值和数组的第(from + 1)个即数组的第二个元素互换，此时数组为 [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10]，此时在基准值 5 前面的元素肯定是小于 5 的，因为第三步已经做了一次比较。后面的元素是未排序的。

我们接下来要做的就是把后面的元素中小于 5 的全部移到 5 的前面。

5.然后我们进入 partition 循环，我们依然以这个数组为例，单独抽出来写个 demo 讲一讲

// 假设代码执行到这里，为了方便演示，我们直接设置 low_end 等变量的值
// 可以直接复制到浏览器中查看数组变换效果
var a = [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10]
var low_end = 1;
var high_start = 10;
var pivot = 5;

console.log('起始数组为', a)

partition: for (var i = low_end + 1; i < high_start; i++) {

    var element = a[i];
    console.log('循环当前的元素为：', a[i])
    var order = element - pivot;

    if (order < 0) {
        a[i] = a[low_end];
        a[low_end] = element;
        low_end++;
        console.log(a)
    }
    else if (order > 0) {
        do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = top_elem - pivot;
        } while (order > 0);

        a[i] = a[high_start];
        a[high_start] = element;

        console.log(a)

        if (order < 0) {
            element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
        }
        console.log(a)
    }
}

console.log('最后的结果为', a)
console.log(low_end)
console.log(high_start)

6.此时数组为 [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10]，循环从第三个元素开始，a[i] 的值为 8，因为大于基准值 5，即 order > 0，开始执行 do while 循环，do while 循环的目的在于倒序查找元素，找到第一个小于基准值的元素，然后让这个元素跟 a[i] 的位置交换。
第一个小于基准值的元素为 1，然后 1 与 8 交换，数组变成  [0, 5, 1, 7, 6, 9, 4, 3, 2, 8, 10]。high_start 的值是为了记录倒序查找到哪里了。

7.此時a[i] 的值變成了1，然後讓1 跟基準值5 交換，數組變成了[0, 1, 5, 7, 6, 9, 4, 3 , 2, 8, 10]，low_end 的值加1，low_end 的值是為了記錄基準值的所在位置。

8.循環接著執行，遍歷第四個元素7，跟第6、7 的步驟一致，數組先變成[0, 1, 5, 2, 6, 9, 4, 3, 7, 8, 10]，再變成[0, 1, 2, 5, 6, 9, 4, 3, 7, 8, 10]

9.遍歷第五個元素6，跟第6、7 的步驟一致，數組先變成[0, 1, 2, 5, 3, 9, 4, 6, 7, 8, 10]，再變成[0, 1, 2, 3, 5, 9, 4, 6, 7, 8, 10]

10.遍歷第六個元素9，跟第6、7 的步驟一致，陣列先變成[0, 1, 2, 3, 5, 4, 9, 6, 7, 8, 10]，再變成[0 , 1, 2, 3, 4, 5, 9, 6, 7, 8, 10]

11.在下一次遍歷中，因為i == high_start，意味著正序和倒序的查找終於找到一起了，後面的元素一定都是大於基準值的，此時退出循環

12.遍歷後的結果為[0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10]，在基準值5 前面的元素都小於5，後面的元素都大於5，然後我們分別對兩個子集進行QuickSort

#13.此時low_end 值為5，high_start 值為6，to 的值仍為10，from 的值仍為0，to - high_start < low_end - from 的結果為true，我們對QuickSort(a, 6, 10)，即對後面的元素進行排序，但是注意，在新的QuickSort 中，因為from - to 的值小於10，所以這次其實是採用了插入排序。所以準確的說，當陣列長度大於 10 的時候，v8 採用了快速排序和插入排序的混合排序方法。

14.然後to = low_end 即設定to 為5，因為while(true) 的原因，會再執行一遍，to - from 的值為5，執行InsertionSort (a, 0, 5)，即對基準值前面的元素執行一次插入排序。

15.因為在 to - from <= 10 的判斷中，有 return 語句，所以 while 迴圈結束。

16.v8 在對陣列進行了一次快速排序後，然後對兩個子集分別進行了插入排序，最終修改數組為正確排序後的數組。

比較

最後來張示意圖感受下插入排序與快速排序：

##圖片來自於https ://www.toptal.com/developers/sorting-algorithms

專題系列

JavaScript專題系列目錄網址：https://github.com/mqyqingfeng/Blog。

JavaScript專題系列預計寫二十篇左右，主要研究日常開發中一些功能點的實現，例如防抖、節流、去重、類型判斷、拷貝、最值、扁平、柯里、遞歸、亂序、排序等，特點是研(chao)究(xi) underscore 和jQuery 的實作方式。

以上是JavaScript中關於 v8 排序原始碼的問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！