[数据结构与算法]漫画算法学习

时间复杂度

算法在运行所消耗的时间

空间复杂度

算法在运行过程中临时占用存储空间大小的量度

数据结构

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效 地访问和修改数据。

线性：数组，链表，栈，队列，哈希表

树：二叉树

图

数组

数组在内存中顺序存储

基本操作

读取，更新，插入(时间复杂度O(n))，删除(时间复杂度O(n))

优点

高效的随机访问能力

缺点

体现在删除和插入两个方面

使用场景

读写多，操作少。二分查找

链表

在内存中随机存储

结构

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由 若干节点（node）所组成。

单向链表的每一个节点又包含两部分，一部分是存放数据的变量 data，另一部分是指向下一个节点的指针next。

双向链表

双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有data 和next指针，还拥有指向前置节点的prev指针。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z2oADclP-1628173057919)(/Users/xinyu/学习/图片/image-20210805215856048.png)]

优点

链表的每一个节点 分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地 利用零散的碎片空间。

基本操作

1. 查找

2. 更新节点

3. 删除元素

   1. 尾部删除
   2. 头部删除
   3. 中间删除

4. 插入节点

   1. 尾部插入

   2. 头部插入

   3. 中间插入

数组VS链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mhb9ObnN-1628173057920)(C:\Users\47\AppData\Roaming\Typora\typora-user-images\image-20210804100557952.png)]

栈和队列

物理结构和逻辑结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xcQqPZR2-1628173057920)(/Users/xinyu/学习/图片/image-20210805215931989.png)]

栈

栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称 FILO）。最早进入的元素存放的位置叫作栈底（bottom），最后进入 的元素存放的位置叫作栈顶（top）。

栈的基本操作

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入 元素，新元素的位置将会成为新的栈顶。

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出 栈，出栈元素的前一个元素将会成为新的栈顶。

队列

队列（queue）是一种线性数据结构，它的特征和行驶车辆的单行 隧道很相似。不同于栈的先入后出，队列中的元素只能先入先出（First In First Out，简称FIFO）。队列的出口端叫作队头（front），队列的入 口端叫作队尾（rear）。

队列的基本操作

入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置 放入元素，新元素的下一个位置将会成为新的队尾。

出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移 出元素，出队元素的后一个元素将会成为新的队头。

栈和队列的应用

栈的应用:栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯， 也就是逆流而上追溯“历史”。

队列的应用:队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回 放，也就是按照“历史”顺序，把“历史”重演一遍。

双端队列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pkrlpDli-1628173057921)(/Users/xinyu/学习/图片/image-20210804193200350.png)]

优先队列：遵循的不是先入先出，而是谁的优先级最高，谁先出队。

散列表

散列表也叫哈希表，是存储Key-Value映射的集合。对于某一个

Key，散列表可以在接近O(1)的时间内进行读写操作。散列表通过哈希

函数实现Key和数组下标的转换，通过开放寻址法和链表法来解决哈希

冲突。

树

定义：树（tree）是n（n≥0）个节点的有限集。当n=0时，称为空树。在

任意一个非空树中，有如下特点。

1. 有且仅有一个特定的称为根的节点。

2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一

个集合本身又是一个树，并称为根的子树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MB1RRqCN-1628173057921)(/Users/xinyu/学习/图片/image-20210804194742842.png)]

树的最大层级数，被称为树的高度或深度。

没有“孩子”，被称为叶子节点

二叉树

定义：二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这

种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能

只有1个，或者没有孩子节点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Hm0oOt5W-1628173057922)(/Users/xinyu/学习/图片/image-20210804195300236.png)]

满二叉树：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点

都在同一层级上，那么这个树就是满二叉树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-svkPZ2Zv-1628173057922)(/Users/xinyu/学习/图片/image-20210804195420426.png)]

完全二叉树：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号

为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n

的节点位置相同，则这个二叉树为完全二叉树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qNgKVB1d-1628173057922)(/Users/xinyu/学习/图片/image-20210804195614357.png)]

二叉树用哪些物理存储来表达？

1. 链式存储结构。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-itslQagq-1628173057922)(/Users/xinyu/学习/图片/image-20210804200043648.png)]

2. 数组。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XxAOiDp7-1628173057923)(/Users/xinyu/学习/图片/image-20210804200108619.png)]

假设一个父节点的下标是parent，那么它的左孩子节点下标就

是2×parent + 1；右孩子节点下标就是2×parent + 2。

二叉树的应用

二叉查找树/二叉排序树

如果左子树不为空，则左子树上所有节点的值均小于根节点的值

如果右子树不为空，则右子树上所有节点的值均大于根节点的值

左、右子树也都是二叉查找树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mPR8i5sQ-1628173057923)(/Users/xinyu/学习/图片/image-20210804212942191.png)]

二叉树的遍历

深度遍历：前序遍历、中序遍历、后序遍历

广度遍历：层序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树。

二叉树的中序遍历，输出顺序是左子树、根节点、右子树。

二叉树的后序遍历，输出顺序是左子树、右子树、根节点。

层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次

关系，一层一层横向遍历各个节点。二叉堆

二叉堆

二叉堆本质上是一种完全二叉树，它分为两个类型。

1. 最大堆。（最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。）

2. 最小堆。 （最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。 ）

二叉堆的自我调整

1. 插入节点。

2. 删除节点。

3. 构建二叉堆。

优先队列实现

先来回顾一下二叉堆的特性。

1. 最大堆的堆顶是整个堆中的最大元素。

2. 最小堆的堆顶是整个堆中的最小元素。

排序算法

1. 时间复杂度为O(n*n)的排序算法

冒泡排序

选择排序插入排序

希尔排序（希尔排序比较特殊，它的性能略优于O(n2)，但又比上O(nlogn)，姑且把它归入本类）

2. 时间复杂度为O(nlogn)的排序算法

快速排序

归并排序

堆排序

3. 时间复杂度为线性的排序算法

计数排序

桶排序

基数排序

冒泡排序

// 编写方法，实现冒泡
    var arr = [29,45,51,68,72,97];
    //外层循环，控制趟数，每一次找到一个最大值
    for (var i = 0; i < arr.length - 1; i++) {
        // 内层循环,控制比较的次数，并且判断两个数的大小
        for (var j = 0; j < arr.length - 1 - i; j++) {
            // 白话解释：如果前面的数大，放到后面(当然是从小到大的冒泡排序)
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
 
    }
    console.log(arr);

快速排序

 function quickSort(arr){
        if(arr.length<1){
            return arr;
        }
        var pivotIndex=Math.floor(arr.length/2);//找到那个基准数
        var pivot=arr.splice(pivotIndex,1)[0]; //取出基准数，并去除，splice返回值为数组。
        var left=[]; 
        var right=[];
        for(var i=0;i<arr.length;i++){
            if(arr[i]<pivot){
                left.push(arr[i]);
            }else{
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat([pivot],quickSort(right)); //加入基准数
    }
    arr=[2,1,5,8,3,7,4,6,9];
    console.log(quickSort(arr)); //[1, 2, 3, 4, 5, 6, 7, 8, 9]