算法
2021/10/26 20:42:09
本文主要是介绍算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
冒泡排序
/* 冒泡排序 */ let arr = [1,5,2,9,8,7,3,4,6]; function sortArray(arr){ let temp; for(let i=0; i<arr.length - 1; i++){ for(let j=0; j<arr.length -1; j++){ if(arr[j]>arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } console.log("原始方法 ========================"); printTime(sortArray, 100000); //改进1:设置标志位pos,每一层排完序之后,就记录排到最大的哪一位在什么位置,因为每一层最大的数就是它所在数组的倒数的位数,下一次就没必要再循环一遍 function sortArray1(arr){ let i = arr.length -1; while(i>0){ let pos = 0; for(let j=0; j<i; j++){ if(arr[j]>arr[j+1]){ pos = j; let temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } i = pos; } } console.log("改进方法1 ========================"); printTime(sortArray1, 100000); //改进2:每趟排序从正反向冒泡一次得到两个最终值(最大和最小值),排序次数几乎减少一半 function sortArray2(arr){ let low = 0; let high = arr.length -1; while(low < high){ for(let i = low; i < high; i++){ if(arr[i]>arr[i+1]){ let temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; } } --high; for(let j = high; j> low; j--){ if(arr[j]<arr[j-1]){ let temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } ++low; } } console.log("改进方法2 ========================"); printTime(sortArray2, 100000); /* 三种方法在数据量为 10000和1000000时的差距如下: 原始方法 ======================== VM1255 algorithm:84 方法耗时: 309 VM1255 algorithm:43 改进方法1 ======================== VM1255 algorithm:84 方法耗时: 183 VM1255 algorithm:75 改进方法2 ======================== VM1255 algorithm:84 方法耗时: 175 VM1255 algorithm:1 undefined algorithm:21 原始方法 ======================== algorithm:84 方法耗时: 34057 algorithm:43 改进方法1 ======================== algorithm:84 方法耗时: 22726 algorithm:75 改进方法2 ======================== algorithm:84 方法耗时: 16544 */ //时间工具 function printTime(func, scope){ let preTime = new Date().getTime(); func(getIntArr(scope)); let curTime = new Date().getTime(); console.log("方法耗时:", curTime-preTime); } //获取一个整型数组 function getIntArr(scope){ let arr = []; for(let i = 0; i<scope; i++){ let temp = parseInt(Math.random()*i); arr.push(temp); } return arr; }
这篇关于算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南