几个常用排序算法简易实现

时间 & 空间 复杂度

算法	时间复杂度	空间复杂度	稳定性
冒泡	O(n^2)	O(1)	稳定
选择	O(n^2)	O(1)	不稳定
插入	O(n^2)	O(1)	稳定
快速	O(nlogn)	logn	不稳定

如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。

1. 执行的次数 -> 空间复杂度 O(x) 简单
2. 算法中通过分析和数学运算得到 T(n) 难

四个便利推导法则：

1. 对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个 循环的时间复杂度为 O(n×m)。
2. 对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是 a, b, c...，则这个循环的时间复杂度为 O(n×a×b×c...)。分析的时候应该由里向外分析这些循环。
3. 对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。
4. 对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。

时间复杂度记忆

1. 冒泡、选择、直接 排序需要两个 for 循环，每次只关注一个元素，平均时间复杂度为 O（n2）O（n2）（一遍找元素 O(n)O(n)，一遍找位置 O(n)O(n)）
2. 快速、归并、希尔、堆基于二分思想，log 以 2 为底，平均时间复杂度为 O(nlogn)O(nlogn)（一遍找元素 O(n)O(n)，一遍找位置 O(logn)O(logn)）

稳定性记忆-“快希选堆”（快牺牲稳定性）

排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。