點擊下載
本文文檔

當前位置：首頁 - 科技 - 知識百科 - 正文

JavaScript中關于v8排序源碼的問題

來源：懂視網責編：小采時間：2020-11-27 20:11:43

JavaScript中關于v8排序源碼的問題

JavaScript中關于v8排序源碼的問題:JavaScript 專題系列第二十篇，也是最后一篇，解讀 v8 排序源碼前言v8 是 Chrome 的 JavaScript 引擎，其中關于數組的排序完全采用了 JavaScript 實現。排序采用的算法跟數組的長度有關，當數組長度小于等于 10 時，采用插入排序，大于 10 的時候，采

推薦度：

點擊下載本文 文檔為doc格式

導讀JavaScript中關于v8排序源碼的問題:JavaScript 專題系列第二十篇，也是最后一篇，解讀 v8 排序源碼前言v8 是 Chrome 的 JavaScript 引擎，其中關于數組的排序完全采用了 JavaScript 實現。排序采用的算法跟數組的長度有關，當數組長度小于等于 10 時，采用插入排序，大于 10 的時候，采

前言

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 的時候采用插入排序。

快速排序

原理

選擇一個元素作為"基準"
小于"基準"的元素，都移到"基準"的左邊；大于"基準"的元素，都移到"基準"的右邊。
對"基準"左邊和右邊的兩個子集，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。

示例

示例和下面的實現方式來源于阮一峰老師的《快速排序（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 的在后面，排序的結果沒有問題?？墒侨绻x擇了第四個元素(也就是第二個 3 )，小于 3 的在基準前面，大于等于 3 的在基準后面，第一個 3 就會被移動到第二個 3 后面，所以快速排序是不穩定的排序。

時間復雜度

阮一峰老師的實現中，基準取的是中間元素，而原地排序中基準取最左邊的元素?？焖倥判虻年P鍵點就在于基準的選擇，選取不同的基準時，會有不同性能表現。

快速排序的時間復雜度最好為 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 在對數組進行了一次快速排序后，然后對兩個子集分別進行了插入排序，最終修改數組為正確排序后的數組。