在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）。所以相應的，我也要修改一下之前的說法了，快速排序算法的核心是分區。