当前位置:首页 > javascript技术文章 > 深入了解javascript 数组的sort方法

详解javascript 数组的sort方法

  • 发布时间:
  • 作者:码农之家原创
  • 点击:153

这篇文章主要知识点是关于javascript、sort、的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下电子书

JavaScript忍者秘籍
  • 类型:JavaScript大小:38.6 MB格式:PDF作者:John
立即下载

深入了解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许可协议发布,转载、演绎必须保留本文的署名周骅,且不得用于商业目的。如您有任何疑问或者授权方面的协商,请与我联系。

以上就是本次给大家分享的关于java的全部知识点内容总结,大家还可以在下方相关文章里找到相关文章进一步学习,感谢大家的阅读和支持。

推荐内容

实例分析ES6中module模块化开发

电商视觉营销设计

SEM长尾搜索营销策略解密

网络规划设计师考试全程指导

赢在大数据

展开 +

收起 -

javascript 相关电子书
学习笔记
网友NO.542259

JavaScript数组排序reverse()和sort()方法详解

JavaScript中数组排序的方法有两个reverse()和sort()。 reverse()方法会反转数组项的顺序: var arr = [1,2,3,4,5]; arr.reverse(); alert(arr); //5,4,3,2,1 sort()方法会按照字符串升序排列数组项,sort()方法会调用每个数组项的tostring()方法,即使数组中的每一项都是数值,sort()方法比较的也是字符串: var arr = [1,2,11,15,5];arr.sort();alert(arr); // 1,11,15,2,5 这种方式在很多情况下并不是最好的方案,因此sort()方法可以接收一个比较函数作为参数。比较函数需要两个参数,如果第一个参数应该位于第二个参数之前则需要返回一个负数,如果两个参数相等则返回0,如果第一个参数应该位于第二个参数之后,则返回一个正数: var arr = [1,2,11,15,5];arr.sort(function(val1,val2){return val1-val2; }); alert(arr); // 1,2,5,11,15 由于比较函数通过返回一个小于零,等于零或大于零的志来影响排序结果,因此减法操作……

网友NO.977102

关于javascript sort()排序你可能忽略的一点理解

前言 在Javascript数组排序中有一个sort()方法,sort()方法可以说分为两种,一种是文字数组排序,一种是数字数组排序。下面这篇文章主要和大家分享了关于最近学习javascript sort()排序发现了一点理解,下面话不多说了,来一起看看详细的介绍吧。 sort()排序的原理 最近在leetcode刷题的时候遇到一个排序问题之前一直都忽略了sort排序的原理,让我们看下w3c对于sort()的说明: 如果调用该方法时没有使用参数,将按字母顺序对数组中的元素进行排序,说得更精确点,是按照字符编码的顺序进行排序。 要实现这一点,首先应把数组的元素都转换成字符串(如有必要),以便进行比较。 这样就可以解释为什么[0,1,5,10,8]的升序排列会是[0,1,10,5,8]了 sort()排序参数的使用 w3c对于参数的使用还有如下一段说明:如果想按照其他标准进行排序,就需要提供比较函数,……

网友NO.954082

JavaScript中数组Array.sort()排序方法详解

JavaScript中数组的sort()方法主要用于对数组的元素进行排序。其中,sort()方法有一个可选参数。但是,此参数必须是函数。 数组在调用sort()方法时,如果没有传参将按字母顺序(字符编码顺序)对数组中的元素进行排序,如果想按照其他标准进行排序,就需要进行传一个参数且为函数,该函数要比较两个值,并且会返回一个用于说明这两个值的相对顺序的数字。 1、对数字数组进行由小到大的顺序进行排序。 代码: var arr = [22,12,3,43,56,47,4];arr.sort();console.log(arr); // [12, 22, 3, 4, 43, 47, 56]arr.sort(function (m, n) { if (m n) return -1 else if (m n) return 1 else return 0});console.log(arr); // [3, 4, 12, 22, 43, 47, 56] 2、对字符串数组执行不区分大小写的字母表排序。 代码: var arr = ['abc', 'Def', 'BoC', 'FED'];console.log(arr.sort()); // ["BoC", "Def", "FED", "abc"]console.log(arr.sort(function(s, t){ var a = s.toLowe……

网友NO.358824

JavaScript中用sort()方法对数组元素进行排序的操作

JavaScript数组sort()方法排序数组的元素。 语法 array.sort( compareFunction ); 下面是参数的详细信息: compareFunction : 指定一个函数,定义排序次序。如果省略,数组字典顺序排序。 返回值: 返回一个排序的数组 例子: htmlheadtitleJavaScript Array sort Method/title/headbodyscript type="text/javascript"var arr = new Array("orange", "mango", "banana", "sugar");var sorted = arr.sort();document.write("Returned string is : " + sorted );/script/body/html 这将产生以下结果: Returned array is : banana,mango,orange,sugar ……

<
1
>

电子书 编程教程 文档 软件 源码 视频

Copyright 2018-2020 xz577.com 码农之家

本站所有电子书资源不再提供下载地址,只分享来路

免责声明:网站所有作品均由会员网上搜集共同更新,仅供读者预览及学习交流使用,下载后请24小时内删除

版权投诉 / 书籍推广 / 赞助:QQ:520161757