JavaScript常用算法

32次阅读

共计 1725 个字符,预计需要花费 5 分钟才能阅读完成。

一、排序算法
1、Array.sort(function)(JavaScript 原生排序算法)参数: 比较函数 (可选) 若无参数, 则按照首字母的 ASCII 码排序, 比较函数的作用为确定排序
function(value1,value2){
if (value1 > value2) {
return 1;
}else if (value1 < value2) {
return -1
}else {
return 0
}
}

按数组中对象的某一属性排序:
function compared(property){
return function(a,b){
let value1 = a[property];
let value2 = b[property];
return value2 – value1;
}
}
array.sort(compared(‘property’));
2、冒泡排序原理:从第一个元素开始依次同相邻元素比较,小于则交换,直到比较完最后一个元素,否则停止,完成一个元素的冒泡行为。循环进入下一元素。核心算法:
for(let i=0;i<arr.length;i++){
let mix = arr[i];
for(let j=i+1;j<arr.length;j++){
if(mix>arr[j]){
[arr[i],arr[j]] = [arr[j],arr[i]];// 交换相邻值
}
}
}

3、选择排序原理:每次选择最大的元素,依次至于末尾。核心算法:
let len = arr.length;
for(let i=0;i<len;i++){
let maxIndex = i;
for(let j=0;j<len-i;j++){
if(arr[maxIndex]<arr[j]){
maxIndex = j;// 记录最大值索引
}
}
[arr[len-1-i],arr[maxIndex]] = [arr[maxIndex],arr[len-1-i]];// 调整最大值位置
}

4、插入排序原理:从第二个元素开始,依次向前插入(插入时前面为有序数列),直到最后一个元素。核心代码:
let len = arr.length;
for(let i=1;i<len;i++){
for(let j=0;j<i;j++){
if(arr[i]<arr[j]){
[arr[j],arr[i]] = [arr[i],arr[j]];
}
}
}
5、快速排序原理:选取一个基准元素,以此分为两组,大于基准元素和小于基准元素组。然后递归两个子数组。最后把数组连接起来。function quickSort(arr){
let len = arr.length;
if(len<=1){// 递归出口
return arr;
}
let mid = Math.floor(len/2)
,left = []
,right = [];
arr.forEach((item)=>{
if(item>arr[mid]){
left.push(item)
}else {
right.push(item)
}
})
let _left = quickSort(left)
,_right = quickSort(right);
retrun left.concat(arr[mid],right)
}
各算法的性能测试:(测试数据来源 https://blog.csdn.net/shuaige…)
数据结果如下
冒泡排序耗时 26000ms 左右
选择排序耗时 5800ms 左右
插入排序耗时 10600ms 左右
归并排序耗时 80-100ms
快速排序 cutoff==5—>30-50mscutoff==10 —>30-60mscutoff==50 —->40-50mscutoff== 3 效果不错 —>30-50ms,30ms 出现的机会很多 cutoff== 0 时(即不在分割长度短的时候转为插入排序),效果依然不错,30-50ms,30ms 出现的很多
堆排序耗时 120-140ms
JavaScript 提供的原生排序耗时 55-70ms
结论
快速排序效率最高,cutoff 取 3 效果最好(没有悬念)
原生排序竟然是第二快的排序算法!诸位同学参加笔试的时候,在没有指明必须要用哪种排序算法的情况下,如果需要排个序,还是用原生的 yourArr.sort(function(a,b){return a-b})吧,毕竟不易错还特别快!

正文完
 0