数据结构

按逻辑进行分类

• 集合： 元素之间没有逻辑关系
• 线性结构（线性表）：一维数组、队列、栈、文件流、字符串
• 非线性结构：树（组织型）、图（区块链型）、多维数组

按存储结构分类

• 顺序存储结构
• 链式存储结构
• 索引存储结构
• 散列存储结构

线性结构可以衍生出其他结构，首尾相接的环。 树分二叉树，遍历分为深度优先（先序、中序、后序）和广度优先，

内存

一维结构、地址、指针、引用、存储结构和内存管理

集合

1. 数据成员是无序的
2. 数据成员不可重复，仅出现一次

线性表

线性结构中的数据元素之间是一对一的关系，数据是一个个排列的

1. 用来存放特定类型的元素
2. 物理结构为顺序表和链表 c语言里操作原生数组（顺序表），步长一致，类型相同，数据整齐排列，只需要计算偏移量 js里面的数组（链式表），顺序是杂乱的，每个元素都封装了一层（链表有首节点，尾结点，可以依据这两个节点进行追溯，链表里存放的是引用，指向内存另一个地址）

线性表衍生结构：栈，队列，串

串只能基于连续表，不能基于链表，串的数据一直存在；对串进行修改和删除都是基于之前的串重新复制的 流是按顺序读数据，读取过的数据，流自动丢弃。

时间复杂度

O(n的平方) 冒泡排序

function bubleSort(arra) {
    var temp;
    for (var i = 0; i < arra.length; i++) {
        for (var j = 0; j < arra.length - i - 1; j++) {
            if (arra[j] > arra[j + 1]) {
                temp = arra[j];
                arra[j] = arra[j + 1];
                arra[j + 1] = temp;
            }
        }
    };
    return arra;
}

O(logn) 二分查找

function binarySearch(arr, target) {
    let max = arr.length - 1
    let min = 0
    while (min <= max) {
        let mid = Math.floor((max + min) / 2)
        if (target < arr[mid]) {
            max = mid - 1
        } else if (target > arr[mid]) {
            min = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

O(nlogn) 归并排序

const mergeSort = array => {
    const len = array.length
    if (len < 2) {
        return len
    }
    const mid = Math.floor(len / 2)
    const first = array.slice(0, mid)
    const last = array.slice(mid)
    return merge(mergeSort(first), mergeSort(last))
    function merge(left, right) {
        var result = [];
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        while (left.length)
            result.push(left.shift());
        while (right.length)
            result.push(right.shift());
        return result;
    }
}