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)


相关推荐

  • 查看端口常用命令以及关闭端口的方法

    查看端口常用命令以及关闭端口的方法dos命令行查询端口常用命令在windows命令行窗口下执行:运行–cmd–netstat-a显示所有活动的TCP连接以及计算机监听的TCP和UDP端口。netstat-e显示以太网发送和接收的字节数、数据包数等。netstat-n以数字形式显示所有活动的TCP连接的地址和端口号。netstat-o显示活动的TCP连接并包括每个连接的进程ID(PID)。netstat-s按协议显示

  • pywin32、win32api、win32gui、win32com、win32con 都是啥?「建议收藏」

    pywin32、win32api、win32gui、win32com、win32con 都是啥?「建议收藏」pywin32、win32api、win32gui、win32com、win32con名称非常类似,特别容易混淆,今天就用600字给大家区分一下文章目录pywin32win32guiwin32conwin32apiwin32com记录时间pywin32pywin32主要的作用是供Python开发者快速调用WindowsAPI的一个模块库。该模块的另一个作用是是通过Python进行COM编程。落地场景:如果你想在Windows操作系统用Python实现自动化工作,pywin32模块经常用到

    2022年10月11日
  • mysql官方监控工具_mysql数据库监控

    mysql官方监控工具_mysql数据库监控spy.properties可以直接到http://my.oschina.net/zh119893/blog/272545复制.P6Spy监控JDBC详细配置说明http://blog.csdn.net/u010280007/article/details/88131401、解压出p6spy.jar和spy.properties两个文件2、将p6spy.jar放入应用程序的WEB-INF…

  • java trylock超时_java trylock以及可中断锁

    java trylock超时_java trylock以及可中断锁线程在调用lock方法来获得另一个线程所持有的锁的时候,很可能发生阻塞。应该更加谨慎地申请锁。tryLock方法试图申请一个锁,在成功获得锁后返回true,否则,立即返回false,而且线程可以立即离开去做其他事。可以调用tryLock时,使用超时参数。lock方法不能被中断。如果一个线程在等待获得一个锁时被中断,中断线程在获得锁之前一直处于阻塞状态。如果出现死锁,那么,lock方法就无法终止。A…

    2022年10月16日
  • ExecuteNonQuery()_sql存储过程返回值

    ExecuteNonQuery()_sql存储过程返回值本文实例讲述了C#中ExecuteNonQuery()返回值注意点。对于C#数据库程序设计有一定的借鉴价值。分享给大家供大家参考之用。具体分析如下:首先,在查询某个表中是否有数据的时候,我们通常用ExecuteNonQuery(),并通过判断值是否大于0来判断数据的存在与否。结果与我所设想的很不一致,调试时才发现,其执行后返回的结果是-1,对此我很是不理解,回头查了下资料,如下显示:SqlComm…

  • 怎么获取股票历史数据?获取股票历史数据Excel

    怎么获取股票历史数据?获取股票历史数据Excel还有吧友在问怎么获取股票历史数据…这个获取股票历史数据Excel的工具再说一次哦!!!亲测可以获取A股、港股、美股所有个股股票历史数据,获取的股票历史数据是Excel文件,方便导入和分析。另外还有A股4000+个股历史数据Excel打包的文件,也是免费的。

发表回复

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

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