深入了解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)。所以相应的,我也要修改一下之前的说法了,快速排序算法的核心是分区。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/81.html