侧边栏壁纸
博主头像
落叶人生博主等级

走进秋风,寻找秋天的落叶

  • 累计撰写 144662 篇文章
  • 累计创建 28 个标签
  • 累计收到 9 条评论
标签搜索

目 录CONTENT

文章目录

常用排序算法的JavaScript实现与性能比较

2023-09-06 星期三 / 0 评论 / 0 点赞 / 14 阅读 / 6774 字

本文收集了几种常用排序方式的JS代码实现与性能比较,包括:冒泡排序,选择排序,插入排序,归并排序和快速排序,我们从实现方式最简单的冒泡排序入手 一、冒泡排序 原理:依次比较两个相邻的项,如果前者大于后

本文收集了几种常用排序方式的JS代码实现与性能比较,包括:冒泡排序,选择排序,插入排序,归并排序和快速排序,我们从实现方式最简单的冒泡排序入手

一、冒泡排序

 原理:依次比较两个相邻的项,如果前者大于后者,则交换两者位置,就如同气泡往上冒一样。

代码实现:

Array.prototype.bubbleSort = function(){	var length = this.length;	for(var i=0;i<length;i++){		for(var j=0;j<length-1-i;j++){			this[j]>this[j+1] && swap(this,j,j+1)  //swap方法交换两个元素		}	}}

注意,内层循环的次数需要减掉外层已循环过的次数,因为外层循环每走一遍就有一个元素被排好序,无需再进行排序。

这种排序方式的时间复杂度为O(n^2),(时间复杂度的计算方法参见http://baike.baidu.com/link?url=DnQgmILQ4dt2kCRwafBtNJHo21upzQVZAX2Y6TyJLoh2rxy_YQtxfhjwhmHmneETaSlw9KuKCjzSJqwGtzL4CUSm4aC3mYTfDlsjfZWCRFiQ8TiPnKHvn3mZ6-YpTkAYX1MEn5BRoFmjOHFRjzNCSK)

,我们可以在http://math.hws.edu/eck/js/sorting/xSortLab.html中模拟这个过程,结果如下:

执行10个长度为10000的乱序数组的排序,总耗时为28.7秒

二、选择排序

原理:从数组中找到最小值,与数组首位交换位置(即放在第一位),接着再寻找第二小的值,放在第二位,以此类推

代码实现:

Array.prototype.selectSort = function(){	var length = this.length, minIndex;	for(var i =0;i<length-1;i++){		minIndex = i;		for(var j=i;j<length;j++){			if(this[minIndex]>this[j])minIndex = j;		}		i !== minIndex) && swap(this,i,minIndex);  //swap方法交换两个元素	}}

这种排序方式的时间复杂度为O(n^2),模拟排序结果如下:

执行10个长度为10000的乱序数组的排序,总耗时为17.7秒

三、插入排序

插入排序分为直接插入排序,二分插入排序和希尔排序,这里介绍的是直接插入排序

原理:将数列的第一个元素视为有序数列,后面都视为无序数列:

{{a1},{a2,a3,a4,…,an}}

然后将无序数列中的元素插入到有序数列的对应位置,插入前通过比大小的方式找到其在有序数列中的对应位置。

Array.prototype.insertSort = function(){	var length = this.length, j, temp;	for(var i=1;i<length;i++){		j = 1;		temp = array[i];  //temp为待排序项		while(j>0 && array[j-1] > temp){  			array[j] = array[j-1];		  			j--;		}		//若temp项之前存在比temp大的项,则把这个项移到当前位置上,		//直到找不到比temp更大的项时,		array[j] = temp				//执行插入操作				}}

这种排序方式的时间复杂度为O(n^2),模拟排序结果如下:

执行10个长度为10000的乱序数组的排序,总耗时为8秒

四、归并排序

从这里开始才是真正能投入实际使用的排序方法,包括最后的快速排序,浏览器一般使用这两种方法之一作为sort函数的实现(但是V8对较短的数组使用插入排序方法)

原理:归并排序采用分治--递归的思想,先对一个数组进行不断的对半拆解,直至子项个数为1。如图:

(原图:http://www.108js.com/article/article5/img/1.png)

之后执行合并,从最下层开始,依次比较左边的项是否比右边的小,是的话移除左数组的第一位并放进新数组中,否则移除右数组的第一位并放进新数组中,这样就可以重新合并出一个排完序的大数组。

代码实现:

function merge(left, right) {		var result = [];		while(left.length > 0 && right.length > 0) {			if(left[0] < right[0]) {				result.push(left.shift());			} else {				result.push(right.shift());			}		}		// 当左右数组长度不等.将比较完后剩下的数组项链接起来即可		console.log(result)		return result.concat(left).concat(right);	}		function mergeSort(array) {		if(array.length == 1) return array;		// 对半划分		var mid = Math.floor(array.length / 2);		var left = array.slice(0, mid);		var right = array.slice(mid);		// 递归合并		return merge(mergeSort(left), mergeSort(right));	}

这种排序方式的时间复杂度为O(n*log n),模拟排序结果如下:

能发现归并排序对大数组的排序效率已经有了质的提升

五、快速排序

原理:首先选取一个基准项(pivot),我们一般选取中间项作为pivot;接着所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。然后对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止

代码实现:

var quickSort = function(arr) {  if (arr.length <= 1) { return arr; }  var pivotIndex = Math.floor(arr.length / 2);  var pivot = arr.splice(pivotIndex, 1)[0];  var left = [];  var right = [];  for (var i = 0; i < arr.length; i++){    if (arr[i] < pivot) {      left.push(arr[i]);    } else {      right.push(arr[i]);    }  }  return quickSort(left).concat([pivot], quickSort(right));};

这里参考了阮一峰老师的文章,详情可移步

http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html

这种排序方式的时间复杂度为O(n*log n),模拟排序结果如下:

与归并排序很接近,对于快速排序与归并排序的性能比较,可参考以下文章:

http://stackoverflow.com/questions/680541/quick-sort-vs-merge-sort

 

广告 广告

评论区