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

日期：2020-05-11 栏目：程序人生浏览：次

这个例子里我完全没管基准元素的位置，一是降低复杂度，另一个原因是下面讨论重复元素处理时，基准元素的位置没什么意义。不过我把最小的值赋给了第一个元素，最大的值赋给了第二个元素，后面处理重复元素时会有帮助。

当然，仅仅是三数取中获得的基准元素，也不见得是可靠的。于是有一些其他的取中值的方法出现。有几种比较典型的手段，一种是平均间隔取一个元素，多个元素取中位数（即多取几个，增加可靠性）；一种是对三数取中进行递归运算，先把大数组平均分成三块，对每一块进行三数取中，会得到三个中值，再对这三个中值取中位数。

不过查阅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之间的元素：

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

相关推荐