JavaScript常用算法

栏目: JavaScript · 发布时间: 4年前

内容简介:1、Array.sort(function)(JavaScript原生排序算法)参数:比较函数(可选)若无参数,则按照首字母的ASCII码排序,比较函数的作用为确定排序

一、 排序 算法

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-50ms

cutoff==10 --->30-60ms

cutoff==50 ---->40-50ms

cutoff==3效果不错--->30-50ms,30ms出现的机会很多

cutoff==0时(即不在分割长度短的时候转为插入排序),效果依然不错,30-50ms,30ms出现的很多

堆排序耗时120-140ms

JavaScript提供的原生排序耗时55-70ms

结论

快速排序效率最高,cutoff取3效果最好(没有悬念)

原生排序竟然是第二快的排序算法!诸位同学参加笔试的时候,在没有指明必须要用哪种 排序算法 的情况下,如果需要排个序,还是用原生的yourArr.sort(function(a,b){return a-b})吧,毕竟不易错还特别快!


以上所述就是小编给大家介绍的《JavaScript常用算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Ajax设计模式

Ajax设计模式

Michael Mahemoff / 杨仁和 / 电子工业出版社 / 2007-5 / 78.00元

★本书荣获LinuxWorld Linux Journal2006年Editors' Choice awards。    ★绝好的一本ajax 高级读物,建议 每个web 程序员都需要买一本,了解什么是真正的好的web设计--网友   [精彩试读一]   [精彩试读二] 本书是一本关于复杂Ajax应用的整体架构设计......一起来看看 《Ajax设计模式》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换