初识排序
    十大排序算法
        选择排序
            冒泡,选择,堆排序,插入,归并,快速,希尔

        其它排序
            计数排序,基数排序,桶排序

冒泡排序（Bubble Sort）
    执行流程（统一以升序为例子）
        1.从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置
            执行完一轮后，最末尾那个元素就是最大的元素

        2.忽略 1 中曾经找到的最大元素，重复执行步骤1，直到全部元素有序

    优化1
        记录是否有发生交换,没有发生交换证明已经排序好

    优化2
        记录最后一次发生交换的索引,索引及之后的数据已经排序好,不需要再次进行判断及交换

排序算法的稳定性（Stability）
    相同元素,排序前后的相对位置没有发生变化,就是稳定的排序算法

原地算法（In-place Algorithm）
    空间复杂度为 𝑂(1) 的都可以认为是原地算法

选择排序（Selection Sort）
    执行流程
        ① 从序列中找出最大的那个元素，然后与最末尾的元素交换位置
            ✓ 执行完一轮后，最末尾的那个元素就是最大的元素
        ② 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①

堆排序（Heap Sort）
    堆排序可以认为是对选择排序的一种优化

    执行流程
        ① 对序列进行原地建堆（heapify）
        
        ② 重复执行以下操作，直到堆的元素数量为1
            ✓ 交换堆顶元素与尾元素
            ✓ 堆的元素数量减 1
            ✓ 对 0 位置进行 1 次 siftDown 操作

插入排序（Insertion Sort）
    执行流程
        ① 在执行过程中，插入排序会将序列分为2部分
            ✓ 头部是已经排好序的，尾部是待排序的

        ② 从头开始扫描每一个元素
            ✓ 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序

    插入排序-优化
        思路是将【交换】转为【挪动】
            ① 先将待插入的元素备份
            ② 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
            ③ 将待插入元素放到最终的合适位置

二分搜索（Binary Search）
    [begin end)
    mid = (begin + end)/2

    [begin mid)
    [mid+1 end)

插入排序优化
    在元素 v 的插入过程中，可以先二分搜索出合适的插入位置，然后再将元素 v 插入
    需要注意的是，使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是 O(n^2)

归并排序（Merge Sort）
    divide
        ① 不断地将当前序列平均分割成2个子序列
        ✓ 直到不能再分割（序列中只剩1个元素）

    merge
        ② 不断地将2个子序列合并成一个有序序列
        ✓ 直到最终只剩下1个有序序列

归并排序原理
-(void)sort{
    [self sortWithBegin:0 end:(int)self.array.count];
}


/// 归并排序divide实现 [begin end) 左闭右开
/// @param begin 起始索引
/// @param end 终止索引
-(void)sortWithBegin:(int)begin end:(int)end{
    //至少要2个元素
    if(end - begin <2) return;
    int mid = (begin+end)>>1;
    
    //拆分左半部分
    [self sortWithBegin:begin end:mid];
    
    //拆分右半部分
    [self sortWithBegin:mid end:end];
    
    //合并左右两部分
    [self mergeWithBegin:begin mid:mid end:end];
}

归并排序实现


复杂度分析
    所以最好、最坏、平均时间复杂度都是 O(nlogn) ，属于稳定排序
    归并排序的空间复杂度是 O n/2 + logn = O(n)
        n/2 用于临时存放左侧数组，logn 是因为递归调用

快速排序（Quick Sort）
    快速排序 – 执行流程

        ① 从序列中选择一个轴点元素（pivot）
        ✓ 假设每次选择 0 位置的元素为轴点元素

        ② 利用 pivot 将序列分割成 2 个子序列
        ✓ 将小于 pivot 的元素放在pivot前面（左侧）
        ✓ 将大于 pivot 的元素放在pivot后面（右侧）
        ✓ 等于pivot的元素放哪边都可以

        ③ 对子序列进行 ① ② 操作
        ✓ 直到不能再分割（子序列中只剩下1个元素）

    快速排序的本质
        逐渐将每一个元素都转换成轴点元素

快速排序的实现
/**
 最好、平均时间复杂度：O(nlogn) 最坏时间复杂度：O(n2)
 由于递归调用的缘故，空间复杂度：O(logn)
 */
-(void)sort{
    
    [self sortWithBegin:0 end:(int)self.array.count];
}



/// 快速排序[beigin end)
/// @param begin 起始index
/// @param end 结束index
-(void)sortWithBegin:(int)begin end:(int)end{
    
    //至少需要两个元素
    if(end - begin<2) return;
    
    //找到轴点元素的位置
    int mid = [self pivotIndexWithBegin:begin end:end];
    
    
    //对左半部分进行快速排序
    [self sortWithBegin:begin end:mid];
    
    
    //对有半部分进行快速排序
    [self sortWithBegin:mid+1 end:end];
    
}




/// 返回轴点元素索引[begin end)
/// @param begin 起始索引
/// @param end 终止索引
-(int)pivotIndexWithBegin:(int)begin end:(int)end{
    
    //为了降低最坏情况的出现概率，一般采取的做法是 随机选择轴点元素
    int randomIndex = begin+ random()%(end - begin);//[begin end)
    [self swapWithIndex1:begin index2:randomIndex];
    
    //备份pivot元素
    id pivot = self.array[begin];
    
    //因为是左闭右开所以end--;
    end--;

    //当begin = end时，结束
    while (begin<end) {
        
        
        while(begin<end){
            //末尾元素大于pivot，end-- 思考：可以将条件改为 <=0 吗？ 不可以
            if ([self compareWithValue1:pivot value2:self.array[end]] < 0) {
                end--;
                
            //末尾元素小于等于pivot,进行交换 begin++
            }else{
                //self.array[begin] = self.array[end];
                [self moveWithFromIndex:end toIndex:begin];
                begin++;
                
                //结束，进入轮换
                break;
            }
        }
        
        
        while(begin<end){
            //起始元素小于末尾元素，begin++ 思考：可以将条件改为 >=0 吗？ 不可以
            if ([self compareWithValue1:pivot value2:self.array[begin]] > 0) {
                begin++;
                
            //起始元素大于等于末尾元素，进行交换，end--
            }else{
                //self.array[end] = self.array[begin];
                [self moveWithFromIndex:begin toIndex:end];
                end--;
                
                //结束，进入轮换
                break;
            }
        }
    }
    
    //放置轴点元素
    self.array[begin] = pivot;
    
    //执行到此处begin == end 返回begin或end都可以。该位置就是pivot的索引
    return begin;
}

希尔排序（Shell Sort）
    希尔排序的效率取决于步长
    希尔本人给出的步长序列是 𝑛/2^𝑘，比如 𝑛 为16时，步长序列是{1, 2, 4, 8}

计数排序（Counting Sort）
    创建一个数组
    数组索引就是要排序的数字
    统计数字出现的次数
    按出现的次数依次写出数字就完成了排序

基数排序（Radix Sort）
    先按个位进行排序
    再按十位进行排序
    再按百位进行排序

桶排序（Bucket Sort）

并查集（Union Find）
    介绍
        查看两个元素是否在同一个集合
        返回元素所在的集合(根节点)
        连接两个集合


    有2种常见的实现思路
        1、Quick Find
        ✓ 查找（Find） 的时间复杂度：O(1)
        ✓ 合并（Union）的时间复杂度：O(n)

        2、Quick Union
        ✓ 查找（Find） 的时间复杂度：O(logn)，可以优化至 O(α(n)) ，α(n) < 5
        ✓ 合并（Union）的时间复杂度：O(logn)，可以优化至 O(α(n)) ，α(n) < 5

并查集（Union Find）实现
    Quick Find
        查找复杂度是O(1)
        合并:遍历所有节点,节点是p1的都改为p2,复杂度是O(n)

    Quick Union
        一直查找到根节点,查找复杂度是O(logn)
        合并:查找到根节点,根节点进行合并O(logn)

并查集（Union Find）优化
    QuickUnion_Size优化
        元素少的树 嫁接到 元素多的树

    QuickUnion_Rank优化
        矮的树 嫁接到 高的树

        节点较多时,树扔很高,在此基础上进一步优化
            QuickUnion_Rank_PathCompression优化
                在find的时路径上所有的节点都指向根节点降低树高,性能开销较大

            QuickUnion_Rank_PathSplitting优化
                使路径上的每个节点都指向其祖父节点（parent的parent）(推荐)

            QuickUnion_Rank_PathHalving优化
                使路径上每隔一个节点就指向其祖父节点（parent的parent）(推荐)

总结
    建议的搭配
        ✓ Quick Union
        ✓ 基于 rank 的优化
        ✓ Path Halving 或 Path Spliting
    可以确保每个操作的均摊时间复杂度为 O(𝛼(𝑛)) ，α(𝑛) < 5

关于自定义类型
    方案一：通过一些方法将自定义类型转为整型后使用并查集（比如生成哈希值）
    方案二：使用链表+映射(Map)

常见数据结构
    线性结构：数组、链表、栈、队列、哈希表
    树形结构：二叉树、B树、堆、Trie、哈夫曼树、并查集
    图形结构

图(Graph)
    图由顶点（vertex）和边（edge）组成，通常表示为 G = (V, E)

    图结构的应用极其广泛
        社交网络
        地图导航
        游戏开发
        ...

图(Graph)的分类
    有向图、无向图、混合图
        出度、入度适用于有向图

    简单图、多重图

    完全图
        无向完全图
        有向完全图

    有权图
        有权图的边可以拥有权值（Weight）

    连通图、强连通图
        无向图 G 中任意2个顶点都是连通的，则称G为连通图
        有向图 G 中任意2个顶点都是连通的，则称G为强连通图   

图的实现方案
    图有2种常见的实现方案
        邻接矩阵（Adjacency Matrix）
            一维数组存放顶点信息
            二维数组存放边信息
            邻接矩阵比较适合稠密图
            不然会比较浪费内存

            邻接矩阵带权图

        邻接表（Adjacency List）
            邻接表存储方式
            邻接表带权图

图的基本接口定义


图的基本接口实现

@interface LCVertex:NSObject
@property(nonatomic,strong)id value;                //顶点值
@property(nonatomic,strong)NSMutableSet * outEdges; //出度边集合
@property(nonatomic,strong)NSMutableSet * inEdges;  //入度边集合
@end

@interface LCEdge : NSObject
@property(nonatomic,strong)id weight;       //权重
@property(nonatomic,  weak)LCVertex* from;  //起始顶点
@property(nonatomic,  weak)LCVertex* to;    //到达顶点
@end

遍历
    图有2种常见的遍历方式（有向图、无向图都适用）
        广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索
        深度优先搜索（Depth First Search，DFS）

广度优先搜索BFS（Breadth First Search）
    介绍
        二叉树层序遍历就是一种广度优先搜索
        与某点直接相连的点，位于该点的下一层。
        广度优先搜索，因为起始点的不同，遍历结果有所不同。同时也不能保证将每一个点都遍历到

    广度优先搜索思路
        使用一个队列,一个节点出队,将其下层节点入队,类似于二叉树的层序遍历

    广度优先搜索-实现
        利用一个NSMutableSet进行去重操作
        使用一个队列,一个节点出队,将其下层节点入队,类似于二叉树的层序遍历

深度优先搜索DFS（Depth First Search）
    介绍
        二叉树前序遍历就是一种深度优先搜索

    深度优先搜索递归实现
        利用一个NSMutableSet进行去重操作
        遍历顶点的出度边,
        递归调用传入 出度边.to 的顶点, 一步一步深入

    深度优先搜索非递归实现
        利用一个NSMutableSet进行去重操作
        利用一个栈放入 边.from 边.to,不断的深入和回溯
        注意continue和break起的作用

AOV网（Activity On Vertex Network）
    以顶点表示活动、有向边表示活动之间的先后关系，这样的图简称为 AOV 网
    标准的AOV网必须是一个有向无环图（Directed Acyclic Graph，简称 DAG）

拓扑排序（Topological Sort）
    可以使用卡恩算法（Kahn于1962年提出）完成拓扑排序


    假设 L 是存放拓扑排序结果的列表
        ① 把所有入度为 0 的顶点放入 L 中，然后把这些顶点从图中去掉
        ② 重复操作 ①，直到找不到入度为 0 的顶点


    代码实现
        一个map存放顶点与入度值的对应关系
        一个队列,记录入度为0的顶点
        出队时更新其它节点的入度值

生成树（Spanning Tree）
    生成树
        也称为支撑树
        连通图的极小连通子图，它含有图中全部的 n 个顶点，恰好只有 n – 1 条边

    最小生成树
        所有生成树中，总权值最小的那棵
        适用于有权的连通图（无向）

切分定理
    给定任意切分，横切边中权值最小的边必然属于最小生成树

Prim算法
    切分定理的应用

Kruskal算法
    按照边的权重顺序（从小到大）将边加入生成树中，直到生成树中含有 V – 1 条边为止（ V 是顶点数量）
    若加入该边会与生成树形成环，则不加入该边

最短路径（Shortest Path）

    有权图
        最短路径是指两顶点之间权值之和最小的路径（有向图、无向图均适用，不能有负权环）

    无权图
        无权图相当于是全部边权值为1的有权图

    负权边
        有负权边，但没有负权环时，存在最短路径

    负权环
        有负权环时，不存在最短路径

    最短路径
        最短路径的典型应用之一：路径规划问题

    求解最短路径的3个经典算法

        单源最短路径算法
            ✓ Dijkstra（迪杰斯特拉算法）
            ✓ Bellman-Ford（贝尔曼-福特算法）

        多源最短路径算法
            ✓ Floyd（弗洛伊德算法）

Dijkstra（迪杰斯特拉算法）
    使用前提：不能有负权边
    
    想象成石头和绳子
        后离开桌面的小石头，都是被先离开桌面的小石头拉起来的

    松弛操作（Relaxation）：更新2个顶点之间的最短路径

Bellman-Ford
    对所有的边进行 V – 1 次松弛操作

Floyd
    对于每一个顶点 k，检查 dist(i，k) + dist(k，j)＜dist(i，j) 是否成立

递归介绍
    递归调用
        递归：函数（方法）直接或间接调用自身。是一种常用的编程技巧

    函数的递归调用过程
        空间复杂度：O(n)
            如果递归调用没有终止，将会一直消耗栈空间
            最终导致栈内存溢出（Stack Overflow）
            所以必需要有一个明确的结束递归的条件
            也叫作边界条件、递归基

    注意：
        使用递归不是为了求得最优解，是为了简化解决问题的思路，代码会更加简洁
        递归求出来的很有可能不是最优解，也有可能是最优解

递归思想
    拆解问题
        把规模大的问题变成规模较小的同类型问题
        规模较小的问题又不断变成规模更小的问题
        规模小到一定程度可以直接得出它的解

    求解
        由最小规模问题的解得出较大规模问题的解
        由较大规模问题的解不断得出规模更大问题的解
        最后得出原来问题的解

    很多链表、二叉树相关的问题都可以使用递归来解决

    使用套路

        ① 明确函数的功能
            先不要去思考里面代码怎么写，首先搞清楚这个函数的干嘛用的，能完成什么功能？

        ② 明确原问题与子问题的关系
            寻找 f(n) 与 f(n – 1) 的关系

        ③ 明确递归基（边界条件）
            递归的过程中，子问题的规模在不断减小，当小到一定程度时可以直接得出它的解
            寻找递归基，相当于是思考：问题规模小到什么程度可以直接得出解？

斐波那契数列
    -(int)fib5:(int)n{
        int first  = 1;
        int second = 1;

        for (int i = 3; i<=n; i++) {
            second = second + first;
            first  = second - first;
            
        }
        return second;
    }

上楼梯
    -(int)climbStairs:(int)n{
        if (n<=2) return n;
        return [self climbStairs:n-1] + [self climbStairs:n-2];
    }

    -(int)climbStairs2:(int)n{
        if (n<=2) return n;
        
        int first  = 1;
        int second = 2;
        
        for (int i = 3; i<=n; i++) {
            second = second + first;
            first  = second - first;
        }
        
        return second;
    }

汉诺塔（Hanoi）
    /// 将n个碟子从p1移动到p3，p2作为辅助柱子
    /// @param n 碟子个数
    /// @param p1 柱子1
    /// @param p2 柱子2
    /// @param p3 柱子3
    -(void)hanoiWithN:(int)n
            pillar1:(NSString*)p1
            pillar2:(NSString*)p2
            pillar3:(NSString*)p3{
        
        if (n==1) {
            [self __move:1 from:p1 to:p3];
            return;
        }
        
        [self hanoiWithN:n-1 pillar1:p1 pillar2:p3 pillar3:p2];
        [self __move:n from:p1 to:p3];
        [self hanoiWithN:n-1 pillar1:p2 pillar2:p1 pillar3:p3];
    }



    /// 移动第n号盘子从from到to
    /// @param n 第n号
    /// @param from 起始柱子
    /// @param to 终止柱子
    -(void)__move:(int)n from:(NSString*)from to:(NSString*)to{
        NSLog(@"%d号：%@ -> %@",n,from,to);
    }

递归转非递归
    若递归调用深度较大，会占用比较多的栈空间，甚至会导致栈溢出
    在有些时候，递归会存在大量的重复计算，性能非常差
    这时可以考虑将递归转为非递归（递归100%可以转换成非递归）

尾调用
    尾调用：一个函数的最后一个动作是调用函数
    如果最后一个动作是调用自身，称为尾递归（Tail Recursion），是尾调用的特殊情况
    尾调用优化也叫做尾调用消除
    平时的递归代码可以考虑尽量使用尾递归的形式

回溯
    什么是回溯
        每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试
        树、图的深度优先搜索（DFS）、八皇后、走迷宫都是典型的回溯应用
    不难看出来，回溯很适合使用递归

八皇后问题(Eight Queens)

八皇后问题代码实现

贪心(Greedy)
    一、贪心
        每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解
        贪心的应用
            哈夫曼树
            最小生成树算法：Prim、Kruskal
            最短路径算法：Dijkstra

    二、最优装载问题（加勒比海盗）

    三、零钱兑换

    四、0-1背包
        ① 价值主导
        ② 重量主导
        ③ 价值密度主导

分治(Divide And Conquer)
    一、分支策略

        分治，也就是分而治之。它的一般步骤是
            ① 将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样）
            ② 子问题又不断分解成规模更小的子问题，直到不能再分解（直到可以轻易计算出子问题的解）
            ③ 利用子问题的解推导出原问题的解
            因此，分治策略非常适合用递归
            需要注意的是：子问题之间是相互独立的

        分治的应用
            快速排序
            归并排序
            Karatsuba算法（大数乘法）

    二、主定理

    三、最大连续子序列和
        定义函数的功能是邱子序列的最大值
        求出跨越了左右两部分的最大值 lrMax
        求出左侧最大值  lMax
        求出右侧最大值  rMax
        三个数中最大的就是要求的和

大数乘法
    用字符串来实现大数相乘。

动态规划（Dynamic Programming）
    动态规划，简称DP
        是求解最优化问题的一种常用策略
        通常的使用套路（一步一步优化）
            ① 暴力递归（自顶向下，出现了重叠子问题）
            ② 记忆化搜索（自顶向下）
            ③ 递推（自底向上）

找零钱

用前边的结果,来推导后面的结果
    dp[i] = dp[i-1] + 1
    dp[i] = dp[i-5] + 1
    dp[i] = dp[i-10] + 1
    dp[i] = dp[i-20] + 1
    最小值就是要的结果

这就是自底向上的原理

动态规划（Dynamic Programming）
    动态规划中的“动态”可以理解为是“会变化的状态”
        ① 定义状态（状态是原问题、子问题的解）
        ✓ 比如定义 dp(i) 的含义

        ② 设置初始状态（边界）
        ✓ 比如设置 dp(0) 的值

        ③ 确定状态转移方程
        ✓ 比如确定 dp(i) 和 dp(i – 1) 的关系

最大连续子序列和
    dp[i] 以i结尾的最大连续子序列和
    如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i]
    如果 dp(i – 1) > 0，那么 dp(i) = dp(i – 1) + nums[i]

最长上升子序列（LIS）
    dp[i] 以i结尾的最长上升子序列的长度 初始状态值为1
    当 nums[i] > nums[j]
    ✓ nums[i] 可以接在 nums[j] 后面，形成一个比 dp(j) 更长的上升子序列，长度为 dp(j) + 1
    ✓ dp(i) = max { dp(i), dp(j) + 1 }

    当 nums[i] ≤ nums[j]
    ✓ nums[i] 不能接在 nums[j] 后面，跳过此次遍历（continue）

最长上升子序列-二分搜索实现

最长公共子序列（Longest Common Subsequence，LCS）
    dp[i,j] 是 nums1前i个元素,与nums2前j个元素的最长公共子序列的长度

    dp[i,0] = 0,dp[0,j]=0;
    nums1[i-1]  = num2s[j-1],那么dp[i,j] = dp[i-1,j-1]+1;
    nums1[i-1] != num2s[j-1],那么dp[i,j] = max(dp[i-1,j],dp[i,j-1]);

代码实现

最长公共子串（Longest Common Substring）
    dp(i, j) 是以 str1[i – 1]、str2[j – 1] 结尾的最长公共子串长度
    dp(i, 0)、dp(0, j) 初始值均为 0
    如果 str1[i – 1] = str2[j – 1]，那么 dp(i, j) = dp(i – 1, j – 1) + 1
    如果 str1[i – 1] ≠ str2[j – 1]，那么 dp(i, j) = 0
    最长公共子串的长度是所有 dp(i, j) 中的最大值 max { dp(i, j) }

0-1背包
    假设 dp(i, j) 是 有前 i 件物品可选，最大承重为 j 时的最大总价值，i ∈ [1, n]，j ∈ [1, W]
    dp(i, 0)、dp(0, j) 初始值均为 0

    分为两种情况，最后一件物品能够装下，不能够装下：
        如果 j < weights[i – 1] 不能够装下：
        那么 dp(i, j) = dp(i – 1, j)

    如果 j ≥ weights[i – 1] 能够装下：
        选择装入： value1 = dp(i – 1, j – weights[i – 1]) + values[i – 1]
        选择不装： value2 = dp(i – 1, j)
        那么 dp(i, j) = max { value1,value2 } 。

0-1背包，恰好装满

布隆过滤器（Bloom Filter）
假设布隆过滤器由 20位二进制、 3 个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引位置

添加元素：将每一个哈希函数生成的索引位置都设为 1

查询元素是否存在
✓ 如果有一个哈希函数生成的索引位置不为 1，就代表不存在（100%准确）
✓ 如果每一个哈希函数生成的索引位置都为 1，就代表存在（存在一定的误判率）

代码实现

跳表(SkipList)
跳表实现
跳表的层数
跳表的复杂度分析

串(Sequence)
蛮力（Brute Force）
KMP
KMP - next表
KMP - 性能分析