JS常见算法小总结

JS常见算法小总结今天与大家一起来测试一下常用算法的性能解析:首先我们创建一个含有十万个数组的数组用来测试:letarray=[];for(leti=0;i<100000;i++){ array.push(i)}接下来我们一起分析各个算法的性能:首先来测试冒泡排序:functionbubbleSort(arr){ for(leti=0;i<a…

大家好,又见面了,我是你们的朋友全栈君。

首先我们创建一个含有十万个数字的数组:

let array = [];
for (let i = 0; i < 100000; i++) { 
   
	array.push(i)
}

接下来我们一起分析各个算法的性能:

首先来测试冒泡排序:
function bubbleSort(arr) { 
   
	for(let i = 0; i < arr.length; i++) { 
   
		for(let j = 0; j < arr.length - i - 1; j++) { 
   
			if(arr[j] > arr[j+1]) { 
   
				let temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr;
}
console.time()
bubbleSort(array);
console.timeEnd()

在这里插入图片描述
可以看到冒泡排序的性能很差。




接下来再来测试选择排序的性能:

function selectionSort(arr) { 
   
	let len = arr.length;
	let minIndex, temp;
	for(let i = 0; i < len - 1; i++) { 
   
		minIndex = i;
		for(var j = i + 1; j < len; j++) { 
   
			if (arr[j] < arr[minIndex]) { 
   
				minIndex = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
	return arr;
}
console.time()
selectionSort(array)
console.timeEnd()

在这里插入图片描述
可以看到比冒泡排序快了一倍。




我们再来测试一下插入排序的性能:


//插入排序 过程就像你拿到一副扑克牌然后对它排序一样
function insertionSort(arr) { 
   
	let len = arr.length;
	let preIndex, current;
	// 我们认为arr[0]已经被排序,所以i从1开始
	for (let i = 1; i < len; i++) { 
   
		preIndex = i - 1;
		current = arr[i];
		while (preIndex >= 0 && arr[preIndex] > current) { 
   
			arr[preIndex + 1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex + 1] = current;
	}
	return arr;
}
console.time()
insertionSort(array)
console.timeEnd()

在这里插入图片描述
?????????????????????????????
才2.96ms????

我弄错了???在测试一下!!!结果还是这个时间左右。如果你认为这个是最快其实就误解了,因为我们现在数组里面的值刚刚好是从小到大排序的所以它才会这么快,如果对我们的这个数组做个反转再来使用插入排序的话,插入排序就会很慢很慢。

当目标是升序排序,最好情况是序列本来已经是升序排序,那么只需比较n-1次,时间复杂度O(n)。最坏情况是序列本来是降序排序,那么需比较n(n-1)/2次,时间复杂度O(n^2)。所以平均来说,插入排序的时间复杂度是O(n^2)。显然,次方级别的时间复杂度代表着插入排序不适合数据特别多的情况,一般来说插入排序适合小数据量的排序。

二分查找

function binary_search(arr, l, r, v) { 
   
	if (l > r) { 
   
		return -1;
	}
	let m = parseInt((l + r) / 2);
	if (arr[m] == v) { 
   
		return m;
	} else if (arr[m] < v) { 
   
		return binary_search(arr, m + 1, r, v);
	} else { 
   
		return binary_search(arr, l, m - 1, v);
	}
}

将二分查找运用到之前的插入排序中,形成二分插入排序。




接下来是快速排序

function qSort(arr) { 
   
	//声名并初始化左边的数组和右边的数组
	let left = [], right = [];
	// 使用数组第一个元素作为基准值
	let base = arr[0];
	//当数组长度只有1或者为空时,直接返回数组,不需要排序
	if (arr.length <= 1) return arr;
	//进行遍历
	for (let i = 1, len = arr.length; i < len; i++) { 
   
		if (arr[i] <= base) { 
   
			//如果小于基准值,push到左边的数组
			left.push(arr[i])
		} else { 
   
		//如果大于基准值,push到右边的数组
			right.push(arr[i]);
		}
	}
	//递归并且合并数组元素
	return [...qSort(left), base, ...qSort(right)];
}

补充:

在这段代码中,我们可以看到,这段代码实现了通过pivot区分左右部分,然后递归的在左右部分继续取pivot排序,实现了快速排序的文本描述,也就是说该的算法实现本质是没有问题的。

虽然这种实现方式非常的易于理解。不过该实现也是有可以改进的空间,在这种实现中,我们发现在函数内定义了left/right两个数组存放临时数据。随着递归的次数增多,会定义并存放越来越多的临时数据,需要Ω(n)的额外储存空间。

因此,像很多算法介绍中,都使用了原地(in-place)分区的版本去实现快速排序,我们先介绍什么是原地分区算法。

原地(in-place)分区算法描述

  1. 从数列中挑选一个元素,称为“基准”(pivot),数组第一个元素的位置作为索引。
  2. 遍历数组,当数组数字小于或者等于基准值,则将索引位置上的数与该数字进行交换,同时索引+1。
  3. 将基准值与当前索引位置进行交换。

通过以上3个步骤,就将以基准值为中心,数组的左右两侧数字分别比基准值小或者大了。这个时候在递归的原地分区,就可以得到已排序后的数组。

原地分区算法实现

//交换数组元素位置
function swap(array, i, j) { 
   
	let temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

function partition(array, left, right) { 
   
	let index = left;
	let pivot = array[right];  //取最后一个数字当做基准值,这样方便遍历
	for (let i = left; i < right; i++) { 
   
		if (array[i] <= pivot) { 
   
			swap(array, index, i);
			index++;
		}
	}
	swap(array, right, index);
	return index;
}

因为我们需要递归的多次原地分区,同时,又不想额外的地址空间所以,在实现分区算法的时候会有3个参数,分别是原数组array,需要遍历的数组起点left以及需要遍历的数组终点right
最后返回一个已经排好序的index值用于下次递归,该索引对应的值一定比索引左侧的数组元素小,比所有右侧的数组元素大。

再次基础上我们还是可以进一步的优化分区算法,我们发现 <=pivot可以改为<pivot,这样可以减少一次交换。

原地分区版快速排序实现

function quickSort(array) { 
   
	function swap(array, i, j) { 
   
		let temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	function partition(array, left, right) { 
   
		let index = left;
		let pivot = array[right];	//取最后一个数字当做基准值,这样方便遍历
		for (let i = left; i < right; i++) { 
   
			if (array[i] < pivot) { 
   
				swap(array, index, i);
				index++;
			}
		}
		swap(array, right, index);
		return index;
	}
	function sort(array, left, right) { 
   
		if (left > right) { 
   
			return;
		}
		let storeIndex = partition(array, left, right);
		sort(array, left, storeIndex - 1);
		sort(array, storeIndex + 1, right);
	}
	sort(array, 0, array.length - 1);
	return array;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/149227.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 数学思想方法-分布式计算-linux/unix技术基础(5)

    数学思想方法-分布式计算-linux/unix技术基础(5)

  • stm32H747_STM32H743的cache

    stm32H747_STM32H743的cache一、H.264的来源和特点H.264是国际标准化组织(ISO)和国际电信联盟(ITU)共同提出的继MPEG4之后的新一代数字视频压缩格式,它即保留了以往压缩技术的优点和精华又具有其它压缩技术无法比拟的许多优点。 1.低码流和MPEG2和MPEG4ASP等压缩技术相比,在同等图像质量下,采用H.264技术压缩后的数据量只有MPEG2的1/8,MPEG4的1/3。 2.高

  • 合理的基尼系数_基尼系数为1表示

    合理的基尼系数_基尼系数为1表示一、基尼指数的概念基尼指数(Gini不纯度)表示在样本集合中一个随机选中的样本被分错的概率。注意:Gini指数越小表示集合中被选中的样本被参错的概率越小,也就是说集合的纯度越高,反之,集合越不纯。当集合中所有样本为一个类时,基尼指数为0.二、基尼系数的计算公式基尼指数的计算公式为:三、计算示例我们分别来计算一下决策树中各个节点基尼系数:以下excel表格记录了Gini系数的计算过程。我们可以看到,GoodBloodCircle的基尼系数是最小的,也就是最不容易犯错误,因此我们应该把这个

    2022年10月13日
  • 联想笔记本电脑键盘灯怎么开启_联想笔记本电脑的键盘背光怎么打开[通俗易懂]

    联想笔记本电脑键盘灯怎么开启_联想笔记本电脑的键盘背光怎么打开[通俗易懂]展开全部1、联想笔记本部分型号具备键盘背光功能,方法通过“FN+空格”打开,支持62616964757a686964616fe78988e69d8331333431336664此功能的机型,键盘上有相应标示。部分早期的Thinkpad笔记本电脑若带有键盘灯,需要通过“Fn+PageUp”组合键开启。发现电脑键盘的“Space(空格键)”按键上有下图所示的标识符号电脑一般带有键盘背光,使用”Fn+…

  • java static关键字的作用_java中static关键字的作用是什么

    java static关键字的作用_java中static关键字的作用是什么java中static关键字的作用:1、java中可以通过statin关键字修饰变量达到全局变量的效果;2、static修饰的方法属于类方法,不需要创建对象就可以调用;3、static代码块常用于初始化静态变量。本文操作环境:windows10系统、java1.8、thinkpadt480电脑。java中static关键字的作用:在java语言中有四种使用情况:成员变量、成员方法、代码块和内部…

  • react 子组件向父组件传值_vue父组件给子组件传值

    react 子组件向父组件传值_vue父组件给子组件传值React子组件给父组件传值

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号