常用排序算法

稳定性分析 稳定排序算法不会在排序后改变相等键值记录间的相对次序。 冒泡排序 交换逆序的相邻关键字 时间复杂度:$O(n^2)$ 改进策略1:设置标志位,若某一轮没有发生交换,则排序结束 改进策略2:第i次遍历范围为0~N-i 插入排序 讲一个记录插入到有序表中,在基本良序的表中性能更好。 时间复杂度:$O(n^2)……

常用查找算法

顺序查找 存储结构为顺序存储或链接存储的线性表 查找的时间复杂度为 $O(N)$ 二分查找 元素必须是有序的 每次将目标值与中间节点的值进行比较,再判断其落入中间节点的左侧或右侧。 可以使用迭代或递归实现。 插值查找 二分查找进阶 联系查字典,将二分查找中的 $mid = \frac{low + high}{2}$ 修改为自适应的 $mid = low + (key - a[low]) / a[high] - a[low]) * (high -low)$ 及将二分查找中的比例……

Leetcode 第180场周赛回顾

Leetcode 第 180 场周赛,又一次 AK(容易满足的我 矩阵中的幸运数 直接遍历就可以实现 使用两个数组分别记录每一行的最小值下标,和每一列的最大值下标。(只需一次遍历即可) 设计一个支持增量操作的栈 使用数组实现的栈,全部都是常规操作。唯一需要注意的或许是增长前k个时范围的特判(当心越界)。 将二叉搜索树变平衡 利用中序遍历获……