深入了解javascript 数组的sort方法(2)

说了这么多，还是实现一个带分区的快速排序吧：

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交换。