算法

本文记录学习算法的相关笔记。

数据结构基础

• 数组：数组是一个固定长度的存储相同数据类型的数据结构，数组中的元素被存储在一段连续的内存空间中。它是最简单的数据结构之一，大多数现代编程语言都内置数组支持。
• 链表：n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来
• 栈：栈可以看作是后进先出的线性表，也就是说，栈的进出顺序是固定的，元素之间的相对位置也是固定的。先存入栈的元素会最后出栈。
• 队列：与栈恰好相反，队列可以看作是先进先出的线性表，这就好比是等车排队，先来的人可以先上车。同样作为线性结构，操作完成之后，元素之间的相对顺序也是固定不变的。
• 二叉查找数(BST)：二分搜索树（英语：Binary Search Tree），也称为二叉搜索树 、有序二叉树或排序二叉树，左子树上所有节点的值都小于它的根节点，右子树上所有的节点的值都大于它的根节点。
• 平衡二叉树(AVL)：在二分搜索树的基础上，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
• 红黑树(R-B Tree)：是平衡二叉树和AVL树的折中。集合类中的Map、关联数组具有较高的查询效率，它们的底层实现就是红黑树。

常见的排序算法

• 选择排序：它的基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
• 插入排序：它的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
• 冒泡排序：一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！
• 希尔排序：希尔排序实质上是一种分组插入排序，即将一个大小为n的数组，为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
• 归并排序：将两个的有序数列合并成一个有序数列，我们称之为"归并"。归并排序(Merge Sort)就是利用归并思想对数列进行排序。