数据结构与算法--基础算法

递归

排序

冒泡排序

插入排序

选择排序

基础排序总结

参考

递归

有两个最难以解的知识点，一个是动态规划，一个是递归
深度优先遍历，前中后序二叉树遍历都会用到递归算法

所有的递归问题都可以用递推公式来表示
f(n) = f(n-1)+1，其中f(1)=1
写递归代码最关键的是写出递推公式，找到终止条件，剩下将递推公式转化为代码就很简单了

递归需要满足三个条件

一个问题的解可以分解成几个子问题的解
这个问题与分解后的子问题，除了数据规模不同，求解思路完全一样
存在递归终止条件

假设有n个台阶，每次可以跨1个台阶或者2个台阶，走这n个台阶有多少走法？

如7个台阶可以，2-2-2-1这样，也可以1-2-1-1-2这样
可以根据第一步的走法把所有走法分两类，
第一类是第一步走了1个台阶，另一类是第一步走了2个台阶
所以，n个台阶的走法等于
先走1阶后 n-1个台阶的走法 + 先走2阶后 n-2个台阶的走法，公式为
f(n) = f(n-1) + f(n-2)
终止条件是f(1)=1，f(2)=2

最后得到的结果是

int f(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    return f(n-1) + f(n-2);
}

写递归代码的关键

找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑分解递归的每个步骤

注意事项

递归代码要警惕堆栈溢出
递归代码要警惕重复计算(*阶问题，可以用hash表保存重复值
递归的空间复杂度很高

*阶的整个计算分解过程如下图

数据结构与算法--基础算法

*阶改成非递归实现

int f(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    int ret = 0;
    int pre = 2;
    int prepre = 1;
    for(int i=3;i<=n;i++) {
        ret = pre + prepre;
        prepre = pre;
        pre = ret;
    }
    return ret;
}

笼统的讲，所有的递归代码都可以改写为迭代循环的非递归写法。
如何做？抽象出递推公式、初始值和边界条件，然后用迭代循环实现。

寻找最终推荐人

/**
   寻找最终推荐人的方式
   不过这段代码有问题
   1.递归可能很深
   2.脏数据情况下可能会死循环
   更高级的处理方式，自动检测A-B-C-A这种环的存在
**/
long findRootReferrerId(long actorId) {
    long referrerId = select referrer_id from [table] where actor_id=actorId;
    if(referrerId == null) return actorId;
    return findRootReferrerId(referrerId);
}

排序

分析一个排序算法的好坏
最好情况，最坏情况，平均情况时间复杂度
时间复杂度的系数，常数，低阶
比较次数和交换(移动)次数
空间复杂度为O(1)的叫原地排序
排序算法的稳定性

稳定排序算法使用的场景
假设有一笔订单，订单有两个属性(下单时间，订单金额)，如有10W条订单数据，按金额从小到大排序，
对于金额相同的订单，按照下单时间从早到晚有序
首先，按照下单时间给订单排序
之后，再用稳定排序算法，按订单金额重新排序
两边排序之后，得到的订单数据就是按金额从小到大排序的，金额相同则按下单时间从早到晚有序

数据结构与算法--基础算法

冒泡排序

空间复杂度是O(1)，是原地排序算法
是稳定排序算法
最好情况时间复杂度是O(n)，最坏是O(n^2)，平均是O(n^2)

有序度是数组中具有有序关系的元素对的个数，有序元素对用数学表达式表示为
有序元素对: a[i] <= a[j]，如果i<j
数据结构与算法--基础算法

对于一个倒排列的数组，如6,5,4,3,2,1 有序度为0，对于一个完全有序的数组如1,2,3,4,5,6，

有序度为n*(n-1)/2，为15，这种叫做满有序度
逆序度正好跟有序度相反(默认从小到大为有序)，其定义如下
逆序元素对：a[i] > a[j]，如果 i<j
关于这三个概念，可以得到一个公式：逆序度 = 满有序度 - 有序度

排序的过程是增加有序度，减少逆序度的过程，最后到达满有序度，说明排序完成
假设待排序的数组初始是 4,5,6,3,2,1 其中有序元素读有(4,5)(4,6)(5,6)，有序度为3，n=6
排序完之后满有序度为 n*(n-1)/2=15

数据结构与算法--基础算法

冒泡排序包含两个操作原子，比较和交换，每交换一次，有序度+1，不管怎么改进，交换次数总是确定的，即逆序度
也就是n*(n-1)/2 初始有序度
对包含n个数据的数组进行冒泡排序，最坏有序度是0，要进行n*(n-1)/2次交换，
最好情况有序度是n*(n-1)/2，不需要交换
平均交换次数可以取中间值 n*(n-1)/4，也就是0(n^2)
这个平均时间复杂度推导过程并不严格，但很多时候很实用