深入了解javascript 數(shù)組的sort方法

在javascript中，數(shù)組對(duì)象有一個(gè)有趣的方法sort，它接收一個(gè)類(lèi)型為函數(shù)的參數(shù)作為排序的依據(jù)。這意味著開(kāi)發(fā)者只需要關(guān)注如何比較兩個(gè)值的大小，而不用管“排序”這件事內(nèi)部是如何實(shí)現(xiàn)的。不過(guò)了解一下sort的內(nèi)部實(shí)現(xiàn)也不是一件壞事，何不深入了解一下呢？

算法課上，我們會(huì)接觸很多種排序算法，什么冒泡排序、選擇排序、快速排序、堆排序等等。那么javascript的sort方法采用哪種排序算法呢？要搞清楚這個(gè)問(wèn)題，呃，直接看v8源代碼好了。v8中對(duì)Array.sort的實(shí)現(xiàn)是采用javascript完成的，粗看下來(lái)，使用了快速排序算法，但明顯比我們熟悉的快速排序要復(fù)雜。那么到底復(fù)雜在什么地方？為什么要搞這么復(fù)雜？這是我們今天要探討的問(wèn)題。

快速排序算法

快速排序算法之所以被稱(chēng)為快速排序算法，是因?yàn)樗苓_(dá)到最佳和平均時(shí)間復(fù)雜度均為O(nlogn)，是一種應(yīng)用非常廣泛的排序算法。它的原理并不復(fù)雜，先找出一個(gè)基準(zhǔn)元素（pivot，任意元素均可），然后讓所有元素跟基準(zhǔn)元素比較，比基準(zhǔn)元素小的，放到一個(gè)集合中，其他的放到另一個(gè)集合中；再對(duì)這兩個(gè)集合執(zhí)行快速排序，最終得到完全排序好的序列。

所以快速排序的核心是不斷把原數(shù)組做切割，切割成小數(shù)組后再對(duì)小數(shù)組進(jìn)行相同的處理，這是一種典型的分治的算法設(shè)計(jì)思路。實(shí)現(xiàn)一個(gè)簡(jiǎn)單的快速排序算法并不困難。我們不妨試一下：

function QuickSort(arr, func) {
	if (!arr || !arr.length) return [];
	if (arr.length === 1) return arr;
	var pivot = arr[0];
	var smallSet = [];
	var bigSet = [];
	for (var i = 1; i < arr.length; i++) {
		if (func(arr[i], pivot) < 0) {
			smallSet.push(arr[i]);
		} else {
			bigSet.push(arr[i]);
		}
	}
	return QuickSort(smallSet, func).concat([pivot]).concat(QuickSort(bigSet, func));
}

這是一個(gè)非?；A(chǔ)的實(shí)現(xiàn)，選取數(shù)組的第一項(xiàng)作為基準(zhǔn)元素。

原地（in-place）排序

我們可以注意到，上面的算法中，我們其實(shí)是創(chuàng)建了一個(gè)新的數(shù)組作為計(jì)算結(jié)果，從空間使用的角度看是不經(jīng)濟(jì)的。javascript的快速排序算法中并沒(méi)有像上面的代碼那樣創(chuàng)建一個(gè)新的數(shù)組，而是在原數(shù)組的基礎(chǔ)上，通過(guò)交換元素位置實(shí)現(xiàn)排序。所以，類(lèi)似于push、pop、splice這幾個(gè)方法，sort方法也是會(huì)修改原數(shù)組對(duì)象的！

我們前面說(shuō)過(guò)，快速排序的核心在于切割數(shù)組。那么如果只是在原數(shù)組上交換元素，怎么做到切割數(shù)組呢？很簡(jiǎn)單，我們并不需要真的把數(shù)組切割出來(lái)，只需要記住每個(gè)部分起止的索引號(hào)。舉個(gè)例子，假設(shè)有一個(gè)數(shù)組[12, 4, 9, 2, 18, 25]，選取第一項(xiàng)12為基準(zhǔn)元素，那么按照原始的快速排序算法，會(huì)把這個(gè)數(shù)組切割成兩個(gè)小數(shù)組：[4, 9, 2], 12, [18, 25]。但是我們同樣可以不切割，先通過(guò)比較、交換元素，將原數(shù)組修改成[4, 9, 2, 12, 18, 25]，再根據(jù)基準(zhǔn)元素12的位置，認(rèn)為0~2號(hào)元素是一組，4~5號(hào)元素是一組，為了表述方便，我這里將比基準(zhǔn)元素小的元素組成的分區(qū)叫小數(shù)分區(qū)，另一個(gè)分區(qū)叫大數(shù)分區(qū)。這很像電腦硬盤(pán)的分區(qū)，并不是真的把硬盤(pán)分成了C盤(pán)、D盤(pán)，而是記錄下一些起止位置，在邏輯上分成了若干個(gè)分區(qū)。類(lèi)似的，在快速排序算法中，我們也把這個(gè)過(guò)程叫做分區(qū)（partition）。所以相應(yīng)的，我也要修改一下之前的說(shuō)法了，快速排序算法的核心是分區(qū)。

說(shuō)了這么多，還是實(shí)現(xiàn)一個(gè)帶分區(qū)的快速排序吧：

function swap(arr, from, to) {
	if (from == to) return;
	var temp = arr[from];
	arr[from] = arr[to];
	arr[to] = temp;
}
 
function QuickSortWithPartition(arr, func, from, to) {
	if (!arr || !arr.length) return [];
	if (arr.length === 1) return arr;
	from = from || 0;
	to = to || arr.length - 1;
	var pivot = arr[from];
	var smallIndex = from;
	var bigIndex = from + 1;
	for (; bigIndex <= to; bigIndex++) {
		if (func(arr[bigIndex], pivot) < 0) {
			smallIndex++;
			swap(arr, smallIndex, bigIndex);
		}
	}
	swap(arr, smallIndex, from);
	QuickSortWithPartition(arr, func, from, smallIndex - 1);
	QuickSortWithPartition(arr, func, smallIndex + 1, to);
	return arr;
}

看起來(lái)代碼長(zhǎng)了很多，不過(guò)并不算復(fù)雜。首先由于涉及到數(shù)組元素交換，所以先實(shí)現(xiàn)一個(gè)swap方法來(lái)處理元素交換。快速排序算法中，增加了兩個(gè)參數(shù)，from和to，分別表示當(dāng)前要處理這個(gè)數(shù)組的哪個(gè)部分，from是起始索引，to是終止索引；如果這兩個(gè)參數(shù)缺失，則表示處理整個(gè)數(shù)組。

同樣的，我用最簡(jiǎn)單的方式選取基準(zhǔn)元素，即所要處理分區(qū)的第一個(gè)元素。然后我定義了smallIndex和bigIndex兩個(gè)變量，分別表示的是左側(cè)小數(shù)分區(qū)的終止索引和右側(cè)大數(shù)分區(qū)的終止索引。什么意思？就是說(shuō)從第一個(gè)元素（基準(zhǔn)元素）到第smallIndex個(gè)元素間的所有元素都比基準(zhǔn)元素小，從第smallIndex + 1到第bigIndex個(gè)元素都比基準(zhǔn)元素大。一開(kāi)始沒(méi)有比較時(shí)，很顯然這兩部分分區(qū)都是空的，而比較的過(guò)程很簡(jiǎn)單，直接是bigIndex向右移，一直移到分區(qū)尾部。每當(dāng)bigIndex增加1，我們會(huì)進(jìn)行一次判斷，看看這個(gè)位置上的元素是不是比基準(zhǔn)元素大，如果大的話(huà)，不用做處理，它已經(jīng)處于大數(shù)分區(qū)了；但如果比基準(zhǔn)元素小，就需要進(jìn)行一次交換。怎么交換呢？首先將smallIndex增加1，意味著小數(shù)分區(qū)增加了一個(gè)元素，但此時(shí)smallIndex位置的元素很明顯是一個(gè)大數(shù)（這個(gè)說(shuō)法其實(shí)不對(duì)，如果之前大數(shù)分區(qū)里面沒(méi)有元素，此時(shí)smallIndex和bigIndex相等，但對(duì)交換沒(méi)有影響），而在bigIndex位置的元素是一個(gè)小數(shù)，所以只要把這兩個(gè)位置的元素交換一下就好了。

最后可別忘了一開(kāi)始的起始元素，它的位置并不正確，不過(guò)只要將它和smallIndex位置的元素交換位置就可以了。同時(shí)我們得到了對(duì)應(yīng)的小數(shù)分區(qū)[from...smallIndex - 1]和大數(shù)分區(qū)[smallIndex + 1...to]。再對(duì)這兩個(gè)分區(qū)遞歸排序即可。

分區(qū)過(guò)程的優(yōu)化

上面的分區(qū)過(guò)程（僅僅）還是有一定的優(yōu)化空間的，因?yàn)樯厦娴姆謪^(qū)過(guò)程中，大數(shù)分區(qū)和小數(shù)分區(qū)都是從左向右增長(zhǎng)，其實(shí)我們可以考慮從兩側(cè)向中間遍歷，這樣能有效地減少交換元素的次數(shù)。舉個(gè)例子，例如我們有一個(gè)數(shù)組[2, 1, 3, 1, 3, 1, 3]，采用上面的分區(qū)算法，一共碰到三次比基準(zhǔn)元素小的情況，所以會(huì)發(fā)生三次交換；而如果我們換個(gè)思路，把從右往左找到小于基準(zhǔn)和元素，和從左往右找到大于基準(zhǔn)的元素交換，這個(gè)數(shù)組只需要交換一次就可以了，即把第一個(gè)3和最后一個(gè)1交換。

我們也來(lái)嘗試寫(xiě)一下實(shí)現(xiàn)：

function QuickSortWithPartitionOp(arr, func, from, to) {
	if (!arr || !arr.length) return [];
	from = from || 0;
	to = to || arr.length - 1;
	if (from >= to - 1) return arr;
	var pivot = arr[from];
	var smallEnd = from + 1;
	var bigBegin = to;
	while (smallEnd < bigBegin) {
		while (func(arr[bigBegin], pivot) > 0 && smallEnd < bigBegin) {
			bigBegin--;
		}
		while (func(arr[smallEnd], pivot) < 0 && smallEnd < bigBegin) {
			smallEnd++;
		}
		if (smallEnd < bigBegin) {
			swap(arr, smallEnd, bigBegin);
		}
	}
	swap(arr, smallEnd, from);
	QuickSortWithPartitionOp(arr, func, from, smallEnd - 1);
	QuickSortWithPartitionOp(arr, func, smallEnd + 1, to);
	return arr;
}

分區(qū)與性能

前面我們說(shuō)過(guò)，快速排序算法平均時(shí)間復(fù)雜度是O(nlogn)，但它的最差情況下時(shí)間復(fù)雜度會(huì)衰弱到O(n2)。而性能好壞的關(guān)鍵就在于分區(qū)是否合理。如果每次都能平均分成相等的兩個(gè)分區(qū)，那么只需要logn層迭代；而如果每次分區(qū)都不合理，總有一個(gè)分區(qū)是空的，那么需要n層迭代，這是性能最差的場(chǎng)景。

那么性能最差的場(chǎng)景會(huì)出現(xiàn)嗎？對(duì)于一個(gè)內(nèi)容隨機(jī)的數(shù)組而言，不太可能出現(xiàn)最差情況。但我們平時(shí)在編程時(shí)，處理的數(shù)組往往并不是內(nèi)容隨機(jī)的，而是很可能預(yù)先有一定順序。設(shè)想一下，如果一個(gè)數(shù)組已經(jīng)排好序了，由于之前的算法中，我們都是采用第一個(gè)元素作為基準(zhǔn)元素，那么必然會(huì)出現(xiàn)每次分區(qū)都會(huì)有一個(gè)分區(qū)為空。這種情況當(dāng)然需要避免。

一種很容易的解決方法是不要選取固定位置的元素作為基準(zhǔn)元素，而是隨機(jī)從數(shù)組里挑出一個(gè)元素作為基準(zhǔn)元素。這個(gè)方法很有效，極大概率地避免了最差情況。這種處理思想很簡(jiǎn)單，我就不另外寫(xiě)代碼了。

然而極大概率地避免最差情況并不等于避免最差情況，特別是對(duì)于數(shù)組很大的時(shí)候，更要求我們?cè)谶x取基準(zhǔn)元素的時(shí)候要更謹(jǐn)慎些。

三數(shù)取中（median-of-three）

基準(zhǔn)元素應(yīng)當(dāng)精心挑選，而挑選基準(zhǔn)元素的一種方法為三數(shù)取中，即挑選基準(zhǔn)元素時(shí)，先把第一個(gè)元素、最后一個(gè)元素和中間一個(gè)元素挑出來(lái)，這三個(gè)元素中大小在中間的那個(gè)元素就被認(rèn)為是基準(zhǔn)元素。

簡(jiǎn)單實(shí)現(xiàn)一下獲取基準(zhǔn)元素的方法：

function getPivot(arr, func, from, to) {
	var middle = (from + to) >> 1;
	var i0 = arr[from];
	var i1 = arr[to];
	var i2 = arr[middle];
	var temp;
	if (func(i0, i1) > 0) {
		temp = i0;
		i0 = i1;
		i1 = temp;
	}
	if (func(i0, i2) > 0) {
		arr[middle] = i0;
		arr[from] = i2;
		arr[to] = i1;
		return i0;
	} else {
		arr[from] = i0;
		if (func(i1, i2) > 0) {
			arr[middle] = i1;
			arr[to] = i2;
			return i1;
		} else {
			arr[middle] = i2;
			arr[to] = i1;
			return i2;
		}
	}
}

這個(gè)例子里我完全沒(méi)管基準(zhǔn)元素的位置，一是降低復(fù)雜度，另一個(gè)原因是下面討論重復(fù)元素處理時(shí)，基準(zhǔn)元素的位置沒(méi)什么意義。不過(guò)我把最小的值賦給了第一個(gè)元素，最大的值賦給了第二個(gè)元素，后面處理重復(fù)元素時(shí)會(huì)有幫助。

當(dāng)然，僅僅是三數(shù)取中獲得的基準(zhǔn)元素，也不見(jiàn)得是可靠的。于是有一些其他的取中值的方法出現(xiàn)。有幾種比較典型的手段，一種是平均間隔取一個(gè)元素，多個(gè)元素取中位數(shù)（即多取幾個(gè)，增加可靠性）；一種是對(duì)三數(shù)取中進(jìn)行遞歸運(yùn)算，先把大數(shù)組平均分成三塊，對(duì)每一塊進(jìn)行三數(shù)取中，會(huì)得到三個(gè)中值，再對(duì)這三個(gè)中值取中位數(shù)。

不過(guò)查閱v8的源代碼，發(fā)現(xiàn)v8的基準(zhǔn)元素選取更為復(fù)雜。如果數(shù)組長(zhǎng)度不超過(guò)1000，則進(jìn)行基本的三數(shù)取中；如果數(shù)組長(zhǎng)度超過(guò)1000，那么v8的處理是除去首尾的元素，對(duì)剩下的元素每隔200左右（200~215，并不固定）挑出一個(gè)元素。對(duì)這些元素排序，找出中間的那個(gè)，并用這個(gè)元素跟原數(shù)組首尾兩個(gè)元素一起進(jìn)行三數(shù)取中。這段代碼我就不寫(xiě)了。

針對(duì)重復(fù)元素的處理

到目前為止，我們?cè)谔幚碓乇容^的時(shí)候比較隨意，并沒(méi)有太多地考慮元素相等的問(wèn)題。但實(shí)際上我們做了這么多性能優(yōu)化，對(duì)于重復(fù)元素引起的性能問(wèn)題并沒(méi)有涉及到。重復(fù)元素會(huì)帶來(lái)什么問(wèn)題呢？設(shè)想一下，一個(gè)數(shù)組里如果所有元素都相等，基準(zhǔn)元素不管怎么選都是一樣的。那么在分區(qū)的時(shí)候，必然出現(xiàn)除基準(zhǔn)元素外的其他元素都被分到一起去了，進(jìn)入最差性能的case。

那么對(duì)于重復(fù)元素應(yīng)該怎么處理呢？從性能的角度，如果發(fā)現(xiàn)一個(gè)元素與基準(zhǔn)元素相同，那么它應(yīng)該被記錄下來(lái)，避免后續(xù)再進(jìn)行不必要的比較。所以還是得改分區(qū)的代碼。

function QuickSortWithPartitionDump(arr, func, from, to) {
	if (!arr || !arr.length) return [];
	from = from || 0;
	to = to || arr.length - 1;
	if (from >= to - 1) return arr;
	var pivot = getPivot(arr, func, from, to);
	var smallEnd = from;
	var bigBegin = to;
	for (var i = smallEnd + 1; i < bigBegin; i++) {
		var order = func(arr[i], pivot);
		if (order < 0) {
			smallEnd++;
			swap(arr, i, smallEnd);
		} else if (order > 0) {
			while (bigBegin > i && order > 0) {
				bigBegin--;
				order = func(arr[bigBegin], pivot);
			}
			if (bigBegin == i) break;
			swap(arr, i, bigBegin);
			if (order < 0) {
				swap(arr, i, smallEnd);
				smallEnd++;
			}
		}
	}
	QuickSortWithPartitionDump(arr, func, from, smallEnd);
	QuickSortWithPartitionDump(arr, func, bigBegin, to);
	return arr;
}

簡(jiǎn)單解釋一下這段代碼，上文已經(jīng)說(shuō)過(guò)，在getPivot方法中，我將比基準(zhǔn)小的元素放到第一位，把比基準(zhǔn)大的元素放到最后一位。定義三個(gè)變量smallEnd、bigBegin、i，從from到smallEnd之間的元素都比基準(zhǔn)元素小，從smallEnd到i之間的元素都和基準(zhǔn)元素一樣大，從i到bigBegin之間的元素都是還沒(méi)有比較的，從bigBegin到to之間的元素都比基準(zhǔn)元素大。了解這個(gè)關(guān)系就好理解這段代碼了。遍歷從smallEnd + 1到bigBegin之間的元素：
* 如果這個(gè)元素小于基準(zhǔn)，那么smallEnd增加1，這時(shí)smallEnd位置的元素是等于基準(zhǔn)元素的（或者此時(shí)smallEnd與i相等），交換smallEnd與i處的元素就可以了。
* 如果這個(gè)元素大于基準(zhǔn)，相對(duì)比較復(fù)雜一點(diǎn)。此時(shí)讓bigBegin減小1，檢查大數(shù)分區(qū)前面一個(gè)元素是不是大于基準(zhǔn)，如果大于基準(zhǔn)，重復(fù)此步驟，不斷讓bigBegin減小1，直到找到不比基準(zhǔn)大的元素（如果這個(gè)過(guò)程中，發(fā)現(xiàn)bigBegin與i相等，則中止遍歷，說(shuō)明分區(qū)結(jié)束）。找到這個(gè)不比基準(zhǔn)大小元素時(shí)需要區(qū)分是不是比基準(zhǔn)小。如果比基準(zhǔn)小，需要做兩步交換，先將i位置的大數(shù)和bigBegin位置的小數(shù)交換，這時(shí)跟第一種case同時(shí)，smallEnd增加1，并且將i位置的小數(shù)和smallEnd位置的元素交換。如果和基準(zhǔn)相等，則只需要將i位置的大數(shù)和bigBegin位置的小數(shù)交換。
* 如果這個(gè)元素與基準(zhǔn)相等，什么也不用做。

小數(shù)組優(yōu)化

對(duì)于小數(shù)組（小于16項(xiàng)或10項(xiàng)。v8認(rèn)為10項(xiàng)以下的是小數(shù)組。），可能使用快速排序的速度還不如平均復(fù)雜度更高的選擇排序。所以對(duì)于小數(shù)組，可以使用選擇排序法要提高性能，減少遞歸深度。

function insertionSort(a, func, 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];
			if (func(tmp, element) > 0) {
				a[j + 1] = tmp;
			} else {
				break;
			}
		}
		a[j + 1] = element;
	}
}

v8引擎沒(méi)有做的優(yōu)化

由于快速排序的不穩(wěn)定性（少數(shù)情況下性能差，前文已經(jīng)詳細(xì)描述過(guò)），David Musser于1997設(shè)計(jì)了內(nèi)省排序法（Introsort）。這個(gè)算法在快速排序的基礎(chǔ)上，監(jiān)控遞歸的深度。一旦長(zhǎng)度為n的數(shù)組經(jīng)過(guò)了logn層遞歸（快速排序算法最佳情況下的遞歸層數(shù)）還沒(méi)有結(jié)束的話(huà)，就認(rèn)為這次快速排序的效率可能不理想，轉(zhuǎn)而將剩余部分換用其他排序算法，通常使用堆排序算法（Heapsort，最差時(shí)間復(fù)雜度和最優(yōu)時(shí)間復(fù)雜度均為nlogn）。

v8引擎額外做的優(yōu)化

快速排序遞歸很深，如果遞歸太深的話(huà)，很可以出現(xiàn)“爆?！?，我們應(yīng)該盡可能避免這種情況。上面提到的對(duì)小數(shù)組采用選擇排序算法，以及采用內(nèi)省排序算法都可以減少遞歸深度。不過(guò)v8引擎中，做了一些不太常見(jiàn)的優(yōu)化，每次我們分區(qū)后，v8引擎會(huì)選擇元素少的分區(qū)進(jìn)行遞歸，而將元素多的分區(qū)直接通過(guò)循環(huán)處理，無(wú)疑這樣的處理大大減小了遞歸深度。我大致把v8這種處理的過(guò)程寫(xiě)一下：

function quickSort(arr, from, to){
  while(true){
    // 排序分區(qū)過(guò)程省略
    // ...
    
    if (to - bigBegin < smallEnd - from) {
      quickSort(a, bigBegin, to);
      to = smallEnd;
    } else {
      quickSort(a, from, smallEnd);
      from = bigBegin;
    }
  }
}

不得不說(shuō)是一個(gè)很巧妙的實(shí)現(xiàn)。

總結(jié)

不知不覺(jué)這篇文章寫(xiě)了這么長(zhǎng)。本來(lái)想對(duì)比各種優(yōu)化之間的性能差異，現(xiàn)在看來(lái)也沒(méi)有什么必要。雖然快速排序算法是一個(gè)很容易很基礎(chǔ)的算法，但我相信很多人并沒(méi)有能夠這么深入地去了解、去優(yōu)化一個(gè)算法。而讀過(guò)了v8引擎對(duì)于這么一個(gè)簡(jiǎn)單算法的實(shí)現(xiàn)后，我發(fā)現(xiàn)它并沒(méi)有簡(jiǎn)單地為了實(shí)現(xiàn)一個(gè)算法而去實(shí)現(xiàn)，而是確確實(shí)實(shí)地盡一切可能去提高算法效率，去消除可能引起性能問(wèn)題的因素。結(jié)論是你真的可以放心地使用Array.sort方法，它的性能令人放心。那么剩下問(wèn)題的就是：作為開(kāi)發(fā)者，我們應(yīng)該如何編寫(xiě)。

本文基于署名-非商業(yè)性使用 3.0許可協(xié)議發(fā)布，轉(zhuǎn)載、演繹必須保留本文的署名周驊，且不得用于商業(yè)目的。如您有任何疑問(wèn)或者授權(quán)方面的協(xié)商，請(qǐng)與我聯(lián)系。