深入了解javascript 數組的sort方法

在javascript中，數組對象有一個有趣的方法sort，它接收一個類型為函數的參數作為排序的依據。這意味著開發者只需要關注如何比較兩個值的大小，而不用管“排序”這件事內部是如何實現的。不過了解一下sort的內部實現也不是一件壞事，何不深入了解一下呢？

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

快速排序算法

快速排序算法之所以被稱為快速排序算法，是因為它能達到最佳和平均時間復雜度均為O(nlogn)，是一種應用非常廣泛的排序算法。它的原理并不復雜，先找出一個基準元素（pivot，任意元素均可），然后讓所有元素跟基準元素比較，比基準元素小的，放到一個集合中，其他的放到另一個集合中；再對這兩個集合執行快速排序，最終得到完全排序好的序列。

所以快速排序的核心是不斷把原數組做切割，切割成小數組后再對小數組進行相同的處理，這是一種典型的分治的算法設計思路。實現一個簡單的快速排序算法并不困難。我們不妨試一下：

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));
}

這是一個非常基礎的實現，選取數組的第一項作為基準元素。

原地（in-place）排序

我們可以注意到，上面的算法中，我們其實是創建了一個新的數組作為計算結果，從空間使用的角度看是不經濟的。javascript的快速排序算法中并沒有像上面的代碼那樣創建一個新的數組，而是在原數組的基礎上，通過交換元素位置實現排序。所以，類似于push、pop、splice這幾個方法，sort方法也是會修改原數組對象的！

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

說了這么多，還是實現一個帶分區的快速排序吧：

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;
}

看起來代碼長了很多，不過并不算復雜。首先由于涉及到數組元素交換，所以先實現一個swap方法來處理元素交換。快速排序算法中，增加了兩個參數，from和to，分別表示當前要處理這個數組的哪個部分，from是起始索引，to是終止索引；如果這兩個參數缺失，則表示處理整個數組。

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

最后可別忘了一開始的起始元素，它的位置并不正確，不過只要將它和smallIndex位置的元素交換位置就可以了。同時我們得到了對應的小數分區[from...smallIndex - 1]和大數分區[smallIndex + 1...to]。再對這兩個分區遞歸排序即可。

分區過程的優化

上面的分區過程（僅僅）還是有一定的優化空間的，因為上面的分區過程中，大數分區和小數分區都是從左向右增長，其實我們可以考慮從兩側向中間遍歷，這樣能有效地減少交換元素的次數。舉個例子，例如我們有一個數組[2, 1, 3, 1, 3, 1, 3]，采用上面的分區算法，一共碰到三次比基準元素小的情況，所以會發生三次交換；而如果我們換個思路，把從右往左找到小于基準和元素，和從左往右找到大于基準的元素交換，這個數組只需要交換一次就可以了，即把第一個3和最后一個1交換。

我們也來嘗試寫一下實現：

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;
}

分區與性能

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

那么性能最差的場景會出現嗎？對于一個內容隨機的數組而言，不太可能出現最差情況。但我們平時在編程時，處理的數組往往并不是內容隨機的，而是很可能預先有一定順序。設想一下，如果一個數組已經排好序了，由于之前的算法中，我們都是采用第一個元素作為基準元素，那么必然會出現每次分區都會有一個分區為空。這種情況當然需要避免。

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

然而極大概率地避免最差情況并不等于避免最差情況，特別是對于數組很大的時候，更要求我們在選取基準元素的時候要更謹慎些。

三數取中（median-of-three）

基準元素應當精心挑選，而挑選基準元素的一種方法為三數取中，即挑選基準元素時，先把第一個元素、最后一個元素和中間一個元素挑出來，這三個元素中大小在中間的那個元素就被認為是基準元素。

簡單實現一下獲取基準元素的方法：

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;
		}
	}
}

這個例子里我完全沒管基準元素的位置，一是降低復雜度，另一個原因是下面討論重復元素處理時，基準元素的位置沒什么意義。不過我把最小的值賦給了第一個元素，最大的值賦給了第二個元素，后面處理重復元素時會有幫助。

當然，僅僅是三數取中獲得的基準元素，也不見得是可靠的。于是有一些其他的取中值的方法出現。有幾種比較典型的手段，一種是平均間隔取一個元素，多個元素取中位數（即多取幾個，增加可靠性）；一種是對三數取中進行遞歸運算，先把大數組平均分成三塊，對每一塊進行三數取中，會得到三個中值，再對這三個中值取中位數。

不過查閱v8的源代碼，發現v8的基準元素選取更為復雜。如果數組長度不超過1000，則進行基本的三數取中；如果數組長度超過1000，那么v8的處理是除去首尾的元素，對剩下的元素每隔200左右（200~215，并不固定）挑出一個元素。對這些元素排序，找出中間的那個，并用這個元素跟原數組首尾兩個元素一起進行三數取中。這段代碼我就不寫了。

針對重復元素的處理

到目前為止，我們在處理元素比較的時候比較隨意，并沒有太多地考慮元素相等的問題。但實際上我們做了這么多性能優化，對于重復元素引起的性能問題并沒有涉及到。重復元素會帶來什么問題呢？設想一下，一個數組里如果所有元素都相等，基準元素不管怎么選都是一樣的。那么在分區的時候，必然出現除基準元素外的其他元素都被分到一起去了，進入最差性能的case。

那么對于重復元素應該怎么處理呢？從性能的角度，如果發現一個元素與基準元素相同，那么它應該被記錄下來，避免后續再進行不必要的比較。所以還是得改分區的代碼。

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;
}

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

小數組優化

對于小數組（小于16項或10項。v8認為10項以下的是小數組。），可能使用快速排序的速度還不如平均復雜度更高的選擇排序。所以對于小數組，可以使用選擇排序法要提高性能，減少遞歸深度。

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引擎沒有做的優化

由于快速排序的不穩定性（少數情況下性能差，前文已經詳細描述過），David Musser于1997設計了內省排序法（Introsort）。這個算法在快速排序的基礎上，監控遞歸的深度。一旦長度為n的數組經過了logn層遞歸（快速排序算法最佳情況下的遞歸層數）還沒有結束的話，就認為這次快速排序的效率可能不理想，轉而將剩余部分換用其他排序算法，通常使用堆排序算法（Heapsort，最差時間復雜度和最優時間復雜度均為nlogn）。

v8引擎額外做的優化

快速排序遞歸很深，如果遞歸太深的話，很可以出現“爆棧”，我們應該盡可能避免這種情況。上面提到的對小數組采用選擇排序算法，以及采用內省排序算法都可以減少遞歸深度。不過v8引擎中，做了一些不太常見的優化，每次我們分區后，v8引擎會選擇元素少的分區進行遞歸，而將元素多的分區直接通過循環處理，無疑這樣的處理大大減小了遞歸深度。我大致把v8這種處理的過程寫一下：

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

不得不說是一個很巧妙的實現。

總結

不知不覺這篇文章寫了這么長。本來想對比各種優化之間的性能差異，現在看來也沒有什么必要。雖然快速排序算法是一個很容易很基礎的算法，但我相信很多人并沒有能夠這么深入地去了解、去優化一個算法。而讀過了v8引擎對于這么一個簡單算法的實現后，我發現它并沒有簡單地為了實現一個算法而去實現，而是確確實實地盡一切可能去提高算法效率，去消除可能引起性能問題的因素。結論是你真的可以放心地使用Array.sort方法，它的性能令人放心。那么剩下問題的就是：作為開發者，我們應該如何編寫。

本文基于署名-非商業性使用 3.0許可協議發布，轉載、演繹必須保留本文的署名周驊，且不得用于商業目的。如您有任何疑問或者授權方面的協商，請與我聯系。