数据结构 - 基础认识

概述 - 排序

插入排序

• 空间：$O(1)$
• 时间：$1 + … + n => O(n^2)$

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 空间：$O(1)$
• 时间：$O(n^2)$

概述 - 树

• 二叉树 -> 左右没有大小关系
• 二叉查找树 -> 左小右大
• AVL 树 -> 平衡二叉查找树
• B 树 -> 平衡查找树
• B+ 树 -> 只有叶子节点有数据的平衡查找树。叶子节点有指针指向下一个节点。
• Tries 树 -> 每个节点一个字符

树与链表、数组对比

• 排好序的数组的查找时间复杂度都是 O(logN)
• 排好序的链表，查找、插入删除都是 O(N)
• 查找树查找，删除，插入基本都是 O(logN)

ps: 数组插入比较麻烦；