JavaScript算法

一、算法复杂度

给定一个或多个已知值，通过一系列的运算输出所需结果的过程，叫做算法。一个需求可能可以通过多种算法来实现，学习算法让我们了解怎样的算法效率更高更快，从而让我们针对某个需求做出最合适的选择。作为一名前端攻城狮，算法可能目前离你很远，但是如果你想在编程的路上走的更远一些，或涉猎到更多的数据逻辑，算法对你的帮助很大。所以想成为一名高端的开发者，算法是必须要学习的。

讨论一个算法的好坏，有最主要的两个方面：该算法所需时间-时间复杂度，该算法占用空间（内存）-空间复杂度。耗时短占用低肯定是最优选择，而往往我们需要在两者中找到一个平衡点。作为一名程序开发者，大多数情况下，时间复杂度比空间复杂度的影响更大一些，能做的改良和优化也更多，所以一般如果不做特别说明，我们在讨论算法复杂度的时候都是指时间复杂度。

1. 时间复杂度

一个算法所需要的时间需要具体上机运行才知道，很显然不可能每个都验证一遍再做选择。我们可以对算法耗时进行合理的预测。

一个算法中语句的执行次数我们叫做时间频度，记做T(n)，n表示问题规模，n增大T(n)也随之增大。而我们预估算法的效率，就是对T(n)的变化趋势进行分析，为了方便分析，我们需要简化一下T(n)函数，所以我们引入时间复杂度的概念：若有某个辅助函数 f(n)，使得当n趋近与无穷大时，T(n)/f(n) 的极限值为不等于0的常数，则称 f(n) 是 T(n)的同数量级函数，记做 T(n) = O( f(n) )。O( f(n) )就是时间复杂度的表示法。

总结一下：用O( f(n) )来表示算法时间复杂度。

2. 复杂度计算举例

理论上，我们对 O( f(n) ) 中的 f(n) 没有写法限制，但是因为我们关注的是随 n 增大复杂度的变化趋势，所以各常数项和系数我们是直接省略不做考虑的。

let a = 1;
let b = 2;
console.log(a+b);
//O(1)

let z = 0;
for(let i=0;i

二、js中常用算法

1.数组整数字去重

//基础写法
function fn(arr){
    let newArr = [...arr];
    for(let i=newArr.length-1;i>=0;i--){
        for(let j=i-1;j>=0;j--){
            if( newArr[i] === newArr[j] ){
                newArr.splice(j,1);
                i --;
            }
        }
    }
    return newArr;
}
//O(n^2)

//优化算法复杂度
function fn(arr){
    let tmp = {};
    let newArr = [];

    for(let i=0,length=arr.length;i

注意：Set结构帮助我们实现去重，不代表复杂度为 1 ，因为内部对数组已经进行了遍历，相当于做了封装。

2. 判断回文

数据结构课程中使用栈结构实现了回文，此处我们讨论一下复杂度。

3. 寻找重复最多字符

let str = "abfsafsafghjiq15445454";

function fn(str){
    let length = str.length;
    let tmp = {};

    for(let i=0;i max ){
            k = [key];
            max = value;
        }else if( value === max ){
            k.push(key);
        }
    }
    return k;
}

console.log(fn(str));
//O(n)

三、排序算法

1. 冒泡排序

动图演示（动图来源visualgo (opens new window)）：

function bubbleSort (arr) {
    let len = arr.length;
    //要进行多少轮排序
    for(let i = 0; i < len-1; i++) {
        //每一轮，相邻两位进行比较，大的放后面
        for(let j = 0; j < len-1-i ; j++) {
            if( arr[j] > arr[j+1] ){
                swap(arr,j,j+1);
            }
        }
    }
}
function swap(arr,i,j){
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

2. 选择排序

动图演示（动图来源visualgo (opens new window)）：

function selectionSort(arr){
    let len = arr.length;
    let minIndex;
    for(let i = 0; i < len ; i++) {
        minIndex = i;
        for(let j = i+1; j < len ; j++) {
            if( arr[j] < arr[minIndex] ){
                minIndex = j;
            }
        }
        swap(arr,i,minIndex);
    }
}
function swap(arr,i,j){
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

3. 插入排序

动图演示（动图来源visualgo (opens new window)）：

function insertSort (arr) {
    let len = arr.length;
    let j;
    let current;
    for(let i = 1; i < len; i++) {
        j = i - 1;
        current = arr[i];
        while(j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
}

4. 快速排序（分治思想）

快速排序是使用分治思想的典型代表。选择一个基准元素，把数组分成左右两部分，左边比基准小，右边比基准大，分别对左右部分递归调用快速排序。

function quickSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    let pivot = arr[0];
    let left = [];
    let right = [];

    for(let i=1;i

平均时间复杂度 O(n log n)，最坏情况 O(n²)，空间复杂度 O(log n)。

5. 归并排序（分治思想）

归并排序也是分治思想，通过递归分割数组并合并排序好的子数组。

function mergeSort(arr){
    if(arr.length <= 1) return arr;

    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
    let result = [];
    let i=0, j=0;

    while(i < left.length && j < right.length){
        if(left[i] <= right[j]){
            result.push(left[i++]);
        }else{
            result.push(right[j++]);
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

时间复杂度稳定为 O(n log n)，空间复杂度为 O(n)。

四、总结

• 算法是为了解决问题而设计的计算步骤；
• 时间复杂度表示算法执行时间随问题规模变化的趋势；
• 常见时间复杂度有 O(1)、O(n)、O(n²)、O(log n)、O(n log n)、O(2^n)等；
• 数组去重、字符串处理、排序等是JS中常用的基础算法；
• 排序算法多样，冒泡、选择、插入、快速、归并各有优缺点，选择时根据实际需求。