v8 是 Chrome 的 JavaScript 引擎，其中關(guān)于數(shù)組的排序完全采用了 JavaScript 實(shí)現(xiàn)。
排序采用的算法跟數(shù)組的長(zhǎng)度有關(guān)，當(dāng)數(shù)組長(zhǎng)度小于等于 10 時(shí)，采用插入排序，大于 10 的時(shí)候，采用快速排序。(當(dāng)然了，這種說(shuō)法并不嚴(yán)謹(jǐn))。
我們先來(lái)看看插入排序和快速排序。
將第一個(gè)元素視為有序序列，遍歷數(shù)組，將之后的元素依次插入這個(gè)構(gòu)建的有序序列中。
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));時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，它考察當(dāng)輸入值大小趨近無(wú)窮時(shí)的情況，一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模 n 的某個(gè)函數(shù)。
最好情況：數(shù)組升序排列，時(shí)間復(fù)雜度為：O(n)
最壞情況：數(shù)組降序排列，時(shí)間復(fù)雜度為：O(n?)
穩(wěn)定性，是指相同的元素在排序后是否還保持相對(duì)的位置。
要注意的是對(duì)于不穩(wěn)定的排序算法，只要舉出一個(gè)實(shí)例，即可說(shuō)明它的不穩(wěn)定性；而對(duì)于穩(wěn)定的排序算法，必須對(duì)算法進(jìn)行分析從而得到穩(wěn)定的特性。
比如 [3, 3, 1]，排序后，還是 [3, 3, 1]，但是其實(shí)是第二個(gè) 3 在 第一個(gè) 3 前，那這就是不穩(wěn)定的排序算法。
插入排序是穩(wěn)定的算法。
當(dāng)數(shù)組是快要排序好的狀態(tài)或者問(wèn)題規(guī)模比較小的時(shí)候，插入排序效率更高。這也是為什么 v8 會(huì)在數(shù)組長(zhǎng)度小于等于 10 的時(shí)候采用插入排序。
選擇一個(gè)元素作為"基準(zhǔn)"
小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。
對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。
示例和下面的實(shí)現(xiàn)方式來(lái)源于阮一峰老師的《快速排序（Quicksort）的Javascript實(shí)現(xiàn)》
以數(shù)組 [85, 24, 63, 45, 17, 31, 96, 50] 為例：
第一步，選擇中間的元素 45 作為"基準(zhǔn)"。（基準(zhǔn)值可以任意選擇，但是選擇中間的值比較容易理解。）
第二步，按照順序，將每個(gè)元素與"基準(zhǔn)"進(jìn)行比較，形成兩個(gè)子集，一個(gè)"小于45"，另一個(gè)"大于等于45"。
第三步，對(duì)兩個(gè)子集不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
// 取數(shù)組的中間元素作為基準(zhǔn)
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));
};然而這種實(shí)現(xiàn)方式需要額外的空間用來(lái)儲(chǔ)存左右子集，所以還有一種原地(in-place)排序的實(shí)現(xiàn)方式。
我們來(lái)看看原地排序的實(shí)現(xiàn)圖示：
為了讓大家看明白快速排序的原理，我調(diào)慢了執(zhí)行速度。
在這張示意圖里，基準(zhǔn)的取值規(guī)則是取最左邊的元素，黃色代表當(dāng)前的基準(zhǔn)，綠色代表小于基準(zhǔn)的元素，紫色代表大于基準(zhǔn)的元素。
我們會(huì)發(fā)現(xiàn)，綠色的元素會(huì)緊挨在基準(zhǔn)的右邊，紫色的元素會(huì)被移到后面，然后交換基準(zhǔn)和綠色的最后一個(gè)元素，此時(shí)，基準(zhǔn)處于正確的位置，即前面的元素都小于基準(zhǔn)值，后面的元素都大于基準(zhǔn)值。然后再對(duì)前面的和后面的多個(gè)元素取基準(zhǔn)，做排序。
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))快速排序是不穩(wěn)定的排序。如果要證明一個(gè)排序是不穩(wěn)定的，你只用舉出一個(gè)實(shí)例就行。
所以我們舉一個(gè)唄~
就以數(shù)組 [1, 2, 3, 3, 4, 5] 為例，因?yàn)榛鶞?zhǔn)的選擇不確定，假如選定了第三個(gè)元素(也就是第一個(gè) 3) 為基準(zhǔn)，所有小于 3 的元素在前面，大于等于 3 的在后面，排序的結(jié)果沒(méi)有問(wèn)題。可是如果選擇了第四個(gè)元素(也就是第二個(gè) 3 )，小于 3 的在基準(zhǔn)前面，大于等于 3 的在基準(zhǔn)后面，第一個(gè) 3 就會(huì)被移動(dòng)到 第二個(gè) 3 后面，所以快速排序是不穩(wěn)定的排序。
阮一峰老師的實(shí)現(xiàn)中，基準(zhǔn)取的是中間元素，而原地排序中基準(zhǔn)取最左邊的元素。快速排序的關(guān)鍵點(diǎn)就在于基準(zhǔn)的選擇，選取不同的基準(zhǔn)時(shí)，會(huì)有不同性能表現(xiàn)。
快速排序的時(shí)間復(fù)雜度最好為 O(nlogn)，可是為什么是 nlogn 呢？來(lái)一個(gè)并不嚴(yán)謹(jǐn)?shù)淖C明：
在最佳情況下，每一次都平分整個(gè)數(shù)組。假設(shè)數(shù)組有 n 個(gè)元素，其遞歸的深度就為 log2n + 1，時(shí)間復(fù)雜度為 O(n)[(log2n + 1)]，因?yàn)闀r(shí)間復(fù)雜度考察當(dāng)輸入值大小趨近無(wú)窮時(shí)的情況，所以會(huì)忽略低階項(xiàng)，時(shí)間復(fù)雜度為：o(nlog2n)。
如果一個(gè)程序的運(yùn)行時(shí)間是對(duì)數(shù)級(jí)的，則隨著 n 的增大程序會(huì)漸漸慢下來(lái)。如果底數(shù)是 10，lg1000 等于 3，如果 n 為 1000000，lgn 等于 6，僅為之前的兩倍。如果底數(shù)為 2，log21000 的值約為 10，log21000000 的值約為 19，約為之前的兩倍。我們可以發(fā)現(xiàn)任意底數(shù)的一個(gè)對(duì)數(shù)函數(shù)其實(shí)都相差一個(gè)常數(shù)倍而已。所以我們認(rèn)為 O(logn)已經(jīng)可以表達(dá)所有底數(shù)的對(duì)數(shù)了，所以時(shí)間復(fù)雜度最后為： O(nlogn)。
而在最差情況下，如果對(duì)一個(gè)已經(jīng)排序好的數(shù)組，每次選擇基準(zhǔn)元素時(shí)總是選擇第一個(gè)元素或者最后一個(gè)元素，那么每次都會(huì)有一個(gè)子集是空的，遞歸的層數(shù)將達(dá)到 n，最后導(dǎo)致算法的時(shí)間復(fù)雜度退化為 O(n?)。
這也充分說(shuō)明了一個(gè)基準(zhǔn)的選擇是多么的重要，而 v8 為了提高性能，就對(duì)基準(zhǔn)的選擇做了很多優(yōu)化。
v8 選擇基準(zhǔn)的原理是從頭和尾之外再選擇一個(gè)元素，然后三個(gè)值排序取中間值。
當(dāng)數(shù)組長(zhǎng)度大于 10 但是小于 1000 的時(shí)候，取中間位置的元素，實(shí)現(xiàn)代碼為：
// 基準(zhǔn)的下標(biāo) // >> 1 相當(dāng)于除以 2 (忽略余數(shù)) third_index = from + ((to - from) >> 1);
當(dāng)數(shù)組長(zhǎng)度大于 1000 的時(shí)候，每隔 200 ~ 215 個(gè)元素取一個(gè)值，然后將這些值進(jìn)行排序，取中間值的下標(biāo)，實(shí)現(xiàn)的代碼為：
// 簡(jiǎn)單處理過(guò)
function GetThirdIndex(a, from, to) {
var t_array = new Array();
// & 位運(yùn)算符
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++;
}
// 對(duì)隨機(jī)挑選的這些值進(jìn)行排序
t_array.sort(function(a, b) {
return comparefn(a[1], b[1]);
});
// 取中間值的下標(biāo)
var third_index = t_array[t_array.length >> 1][0];
return third_index;
}也許你會(huì)好奇 200 + ((to - from) & 15) 是什么意思？
& 表示是按位與，對(duì)整數(shù)操作數(shù)逐位執(zhí)行布爾與操作。只有兩個(gè)操作數(shù)中相對(duì)應(yīng)的位都是 1，結(jié)果中的這一位才是 1。
以 15 & 127 為例：
15 二進(jìn)制為： （0000 1111）
127 二進(jìn)制為：（1111 1111）
按位與結(jié)果為：（0000 1111）＝ 15
所以 15 & 127 的結(jié)果為 15。
注意 15 的二進(jìn)制為： 1111，這就意味著任何和 15 按位與的結(jié)果都會(huì)小于或者等于 15，這才實(shí)現(xiàn)了每隔 200 ~ 215 個(gè)元素取一個(gè)值。
終于到了看源碼的時(shí)刻！源碼地址為：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)我們以數(shù)組 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 為例，分析執(zhí)行的過(guò)程。
1.執(zhí)行 QuickSort 函數(shù) 參數(shù) from 值為 0，參數(shù) to 的值 11。
2.10 < to - from < 1000 第三個(gè)基準(zhǔn)元素的下標(biāo)為 (0 + 11 >> 1) = 5，基準(zhǔn)值 a[5] 為 5。
3.比較 a[0] a[10] a[5] 的值，然后根據(jù)比較結(jié)果修改數(shù)組，數(shù)組此時(shí)為 [0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10]
4.將基準(zhǔn)值和數(shù)組的第(from + 1)個(gè)即數(shù)組的第二個(gè)元素互換，此時(shí)數(shù)組為 [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10]，此時(shí)在基準(zhǔn)值 5 前面的元素肯定是小于 5 的，因?yàn)榈谌揭呀?jīng)做了一次比較。后面的元素是未排序的。
我們接下來(lái)要做的就是把后面的元素中小于 5 的全部移到 5 的前面。
5.然后我們進(jìn)入 partition 循環(huán)，我們依然以這個(gè)數(shù)組為例，單獨(dú)抽出來(lái)寫個(gè) demo 講一講
// 假設(shè)代碼執(zhí)行到這里，為了方便演示，我們直接設(shè)置 low_end 等變量的值
// 可以直接復(fù)制到瀏覽器中查看數(shù)組變換效果
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('起始數(shù)組為', a)
partition: for (var i = low_end + 1; i < high_start; i++) {
var element = a[i];
console.log('循環(huán)當(dāng)前的元素為：', 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('最后的6.此時(shí)數(shù)組為 [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10]，循環(huán)從第三個(gè)元素開(kāi)始，a[i] 的值為 8，因?yàn)榇笥诨鶞?zhǔn)值 5，即 order > 0，開(kāi)始執(zhí)行 do while 循環(huán)，do while 循環(huán)的目的在于倒序查找元素，找到第一個(gè)小于基準(zhǔn)值的元素，然后讓這個(gè)元素跟 a[i] 的位置交換。
第一個(gè)小于基準(zhǔn)值的元素為 1，然后 1 與 8 交換，數(shù)組變成 [0, 5, 1, 7, 6, 9, 4, 3, 2, 8, 10]。high_start 的值是為了記錄倒序查找到哪里了。
7.此時(shí) a[i] 的值變成了 1，然后讓 1 跟 基準(zhǔn)值 5 交換，數(shù)組變成了 [0, 1, 5, 7, 6, 9, 4, 3, 2, 8, 10]，low_end 的值加 1，low_end 的值是為了記錄基準(zhǔn)值的所在位置。
8.循環(huán)接著執(zhí)行，遍歷第四個(gè)元素 7，跟第 6、7 的步驟一致，數(shù)組先變成 [0, 1, 5, 2, 6, 9, 4, 3, 7, 8, 10]，再變成 [0, 1, 2, 5, 6, 9, 4, 3, 7, 8, 10]
9.遍歷第五個(gè)元素 6，跟第 6、7 的步驟一致，數(shù)組先變成 [0, 1, 2, 5, 3, 9, 4, 6, 7, 8, 10]，再變成 [0, 1, 2, 3, 5, 9, 4, 6, 7, 8, 10]
10.遍歷第六個(gè)元素 9，跟第 6、7 的步驟一致，數(shù)組先變成 [0, 1, 2, 3, 5, 4, 9, 6, 7, 8, 10]，再變成 [0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10]
11.在下一次遍歷中，因?yàn)?i == high_start，意味著正序和倒序的查找終于找到一起了，后面的元素肯定都是大于基準(zhǔn)值的，此時(shí)退出循環(huán)
12.遍歷后的結(jié)果為 [0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10]，在基準(zhǔn)值 5 前面的元素都小于 5，后面的元素都大于 5，然后我們分別對(duì)兩個(gè)子集進(jìn)行 QuickSort
13.此時(shí) low_end 值為 5，high_start 值為 6，to 的值依然是 10，from 的值依然是 0，to - high_start < low_end - from 的結(jié)果為 true，我們對(duì) QuickSort(a, 6, 10)，即對(duì)后面的元素進(jìn)行排序，但是注意，在新的 QuickSort 中，因?yàn)?from - to 的值小于 10，所以這一次其實(shí)是采用了插入排序。所以準(zhǔn)確的說(shuō)，當(dāng)數(shù)組長(zhǎng)度大于 10 的時(shí)候，v8 采用了快速排序和插入排序的混合排序方法。
14.然后 to = low_end 即設(shè)置 to 為 5，因?yàn)?while(true) 的原因，會(huì)再執(zhí)行一遍，to - from 的值為 5，執(zhí)行 InsertionSort(a, 0, 5)，即對(duì)基準(zhǔn)值前面的元素執(zhí)行一次插入排序。
15.因?yàn)樵?to - from <= 10 的判斷中，有 return 語(yǔ)句，所以 while 循環(huán)結(jié)束。
16.v8 在對(duì)數(shù)組進(jìn)行了一次快速排序后，然后對(duì)兩個(gè)子集分別進(jìn)行了插入排序，最終修改數(shù)組為正確排序后的數(shù)組。
最后來(lái)張示意圖感受下插入排序和快速排序：
圖片來(lái)自于 https://www.toptal.com/developers/sorting-algorithms
JavaScript專題系列目錄地址：https://github.com/mqyqingfeng/Blog。
JavaScript專題系列預(yù)計(jì)寫二十篇左右，主要研究日常開(kāi)發(fā)中一些功能點(diǎn)的實(shí)現(xiàn)，比如防抖、節(jié)流、去重、類型判斷、拷貝、最值、扁平、柯里、遞歸、亂序、排序等，特點(diǎn)是研(chao)究(xi) underscore 和 jQuery 的實(shí)現(xiàn)方式。
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
Copyright ? 2019-2025 51dongshi.com 版權(quán)所有
違法及侵權(quán)請(qǐng)聯(lián)系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市萬(wàn)商天勤律師事務(wù)所王興未律師提供法律服務(wù)
