最长上升子队列
将问题看作有向无环图寻找最长的路径。每两个具有上升顺序的数字作为一条有向边，边权重设置为-1。将整个问题分解为从每个节点寻找最短路径（边权重为负）。每个节点的最短路径中最小值即位最长上升队列。复杂度O（$N^3$）。
以上方法是存在冗余的，一些节点的最短路径问题是另一些节点的子问题。
改进：按顺序计算以每个节点为结尾的最长子序列，并暂存，迭代地利用之前的所找到的路径每遇到到结尾节点更长的序列就替换更新。复杂度为O（$N^2$）
基本排序
顺序关系通常借助compare方法实现。默认顺序指的是升序。
选择/冒泡排序(select heap):每次从剩序乱序列中最小元素放到序列首。复杂度为O($N^2$)。运行时间与输入数据无关。
堆排序（heap sort）：可以维护一个堆（最大堆)来加快每次寻找最小元素的速度。每次删除最大值，并将其放在堆对应数组尾的空位置。可以通过方法来减少额外的内存消耗。堆的定义可以看上一节
原地堆排序：先将原数字整理成最大堆的形式（以反向层级顺序下沉形成最大堆），再借助下沉方法进行排序。
它是我们所知的唯一能够同时最优地利用空间和时间的方法。现代系统的许多应用 很少使用它，因为它无法利用缓存。数组元素很少和相邻的其他元素进行比较，因此缓存未命中的次 数要远远高于大多数比较都在相邻元素间进行的算法。
归并排序（merge sort）：不断将原数组分割排序然后合并至新的数组中去的递归算法。
将任意长度为 N 的数组排序所需时间和 $NlogN$ 成正比；
它的主要缺点则是它所需的额外空间和 N 成正比。对于分割后的小规模数据可以转而使用插入排序来提高速度。归并排序的主要缺点是辅助数组所使用的额外空间和 N 的大小成正比。
插入排序（insertion sort）：在保持数组前面的元素有序的情况下，将后面的元素一一加入。通过使用交换方法可以避免额外的内存占用。
插入排序所需的时间取决于输入中元素的初始顺序。最坏的情况下时间复杂度为O($N^2$)
希尔排序（shell sort）：希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。希尔排序就是使得数组从h有序接近到1有序（即排序完成）的算法。
它的运行时间达不到平方级别。
快速排序：快速排序是一种分治的排序算法。它选择一个切分元素，将一个数组分成大于切分元素和小于切分元素的两个子数组，不断递归将各部分独立地排序，最终便可以得到有序的原数组。（因此快速排序可以看作二叉搜索树排序）。
快速排序特点包括它是原地排序（只需要一个很小的辅助栈），且将长度为 N 的数组排序所需的时间和 NlgN 成正比。主要缺点是非常脆弱，在切分不平衡时这个程序可能会极为低效。在实现时要非常小心才能避免低劣的性能。在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的位置取决于数组的内容。快速排序各个部分排序完成之后原数组自然有序。
- 切分【alg:288-296】：随意得选取左端值为切分元素，从数组的左端开始向右扫描直到找到一个大于等 于它的元素，再从数组的右端开始向左扫描直到找到一个 小于等于它的元素，交换两者的位置。最后交换切分元素的位置。
三向切分的快速排序：递归地将数组分为三部分（比比较元素小，与比较元素相等和大于比较元素）
这种方法存在较多重复元素的序列的排序效果较好。
处理快速排序所存在问题的方法
- 随机性:在排序之前选择一个随机的切分元素或是数组随机。
- 更聪明的枢轴选择:计算或近似中位数。
- 自省:如果递归深入，则切换到更安全的排序，比如插入排序。
排序的稳定性指的是：在稳定排序时，等价项不会“交叉”。排序算法不仅能够整理数字的顺序同时提高其他任务解决的效率。基于比较的排序算法的时间复杂度的下界在$lg (N!)-Nlg(N)$之间。
基排序（radix sort）
相对于归并排序的比较，转而统计元素出现的顺序。利用空间而不进行比较。
计数排序
- 频率统计
- 将频率转换为索引（累加形式） 确定写一个新的字符串起始的索引位置
- 数据分类
- 回写
低位优先排序LSD
字符串每个字符都可以转换为数字（ascII等）。从低位到高位（从左向右）对每个字符使用计数排序最后得到有序的序列。
对于基于 R 个字符的字母表的 N 个以长为 W 的字符串为键的元素，复杂度度为W（N+R）。
当键长度不同时将高位视为空即可。
算法流程（迭代）
- 计算当前位置各个值的出现频率
- 将频率转换为索引
- 将元素分类
- 回写
高位优先排序MSD
从高位到低位计数排序可以避免许多冗余计数和分类。
对于长度不同的字符串，将所有字符都已被检查过的字符串所在的子数组排在所有子数组的前面，这样就不需要递归地将该子数组排序。当对长度不同的数字进行排序时一般在数字前补0，而对于字符串一般再后面补。
与堆排序缺点相似，算法的缓存性能较差。
算法流程（递归）
- 对高位进行排序；
- 对高位相同的右侧子字符串进行排序；
单词查找树（Trie）
单词查找树也是由链接的结点所组成的数据结构，这些链接可能为空，也可能指向其他结点。每个节点有一个父节点以及R个链接。其中 R 为字母表的大小。因此，单词查找树一般都含有大量的空链接。将每个键所关联的值保存在该键的最后一个字母所对应的结点中。
由于含有许多空链接，当字母表R的数量较大时会占用较大的空间。
单词查找树的链表结构（形状）和键的插入或删除顺序无关：对于任意给定的一组键，其单词查找树都是唯一的。
在单词查找树中查找一个键或是插入一个键时，访问数组的次数最多为键的长度加 1。
一棵单词查找树中的链接总数在 RN 到 RNw 之间，其中 w 为键的平均长度。
三向单词查找树（TST）
在三向单词查找树中，每个结点都含有一个字符、 三条链接和一个值。这三条链接分别对应着当前字母小于、等于和大于结点字母的所有键。
在一棵由 N 个随机字符串构造的三向单词查找树中，查找未命中平均需要比较字符$lnN$次。除$lnN$次外， 一次插入或命中的查找会比较一次被查找的键中的每个字符。
