算法

数据结构是靠谱算法的前提。从数组到链表以及其他由链式结构衍生的数据结果，或者是树，都是在特定情景下伴随着特定的算法产生，这些数据结果或者是算法解决的是时间、空间和易用性的问题。

查找和排序又是两大基本算法问题，也是其他诸如压缩、加密等算法的基础。判断算法优劣的标准和上面说的算法解决的问题一致，在不同的问题或者是情景下所偏向的点也会有不同。但是关于算法的评价流程永远的存在标准，或者说指导方法是确定的，当然这些指导方法不仅局限与算法，而可以适用于所有科学研究上：

算法经典问题： 排序 & 查找。

排序

初级排序方法通常是选择和插入排序，定位为初级的原因是时间复杂度是O(N平方)，也就是暴力方式的复杂度，通常来讲是存在普适的排序方案的（前提是数据和规则等是未知），比如快排。选择排序可以说是所有排序是实现的基础，思路是通过两个for循环遍历带排序集合的所有位置并找到这个位置与这个位置之后的元素中的最小者并与之交换。但是，极端情况下当集合本身有序时，选择排序的时间复杂度仍然没有变，其比较次数仍然是N平方，此时针对于这种特定属性或者是部分符合此属性的集合来讲，选择插入排序更适合，插入排序同样是通过双for循环，但是其从后向前找到元素的在此元素之前集合中的位置，减少了向前比较的次数，从而减小了时间复杂度，在集合本身有序的情况下，这种复杂度是N-1。

从平方复杂度到指数对数级别就是初级排序算法与高级算法的分水岭，其中后者经典排序算法包含：归并、快排、堆排序等。归并和快排通过分治&递归的方式完成，前者核心在于归并merge，后者在于partition，因为merge操作需要额外的空间与复制时间等因素，相比较而言快排更快。

至此，从初级排序到高级排序，解决的是时间的问题，从平方到常数对数，但是对于解决巨大数据量下的TopM问题，当数据大到无法再内存中存储时即使效率再高，也无法使用。数据结构「优先队列」可以用来解决这种问题，需要注意的是，优先队列内部并非是有序的，但是每次通过insert 和 deleteMax/deleteMin的方式插入并且删除最大/最小元素的方式就可以实现Top问题的求解。优先队列使用数据结构「二叉堆」表示，二叉堆是完全二叉树（最下面一层的结点都集中在该层最左边的若干位置的二叉树），且根节点大于他的两个子节点，因为这种特性，用数组便可以实现二叉堆。

查找

查找的数据结构基础是：二叉查找树、红黑树、散列表。当然可以从最简单的数据结构开始说起，看看实现快速查找的复杂度。

首先，可以试试无序链表，插入O(1)，查找O(N)。那么，如果换做有序链表呢，当然查找可以达到O(logN)，但是插入是O(N)。所以实现查找的数据结构的诉求是高效的查找以及灵活的插入，并且能够实现一些如最大、最小、范围这类有序操作。二叉查找树(BST)这种数据结构可以做到在logN复杂度上的插入和查找操作。BST的问题是极端情况下其变为了有序链表，而平衡二叉查找树可以在存在数据平衡查找树（左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1）通过插入和删除时的平衡操作保持树的平衡，这种灵活性使用2-3树这种结构更易实现，红黑二叉查找树是这种2-3树的完美实现，其中红节点表示2-3树的3节点，黑节点为2节点。

另一种可以用来快速查找的数据结构是散列表，空间换时间的思路是其能够在最低的复杂度下进行插入、查找操作。

关于算法，还有一类经典情景是有关字符串的排序与查找，以及如子串查找这类KMP算法等。

…