排序算法
1 冒泡算法:冒泡排序是稳定的,时间复杂度是平方复杂度。
核心原理:相邻元素两两间进行比较,按照升序或降序的关系互换位置。
比如在升序排序中,将大的放在后面,小的放在前面。
2 选择排序:选择排序是稳定的,时间复杂度是平方复杂度。
核心原理:从数据集合中选出最小(大)的一个元素,存放在序列的起始位置,再从剩余的未排序元素中寻找到最小(大)的元素,
放到已排序的序列的末尾。不断重复这样的过程,直至实现排序。
3 计数排序:计数排序是稳定的,时间复杂度是线性复杂度。
核心原理:利用顺序表的索引天然有序的原理,将数值映射到表中的索引,即可实现排序。
4 桶排序:桶排序是稳定的,时间复杂度是线性复杂度。
核心原理:桶排序是对简单桶排序(计数排序)的优化。对桶排序进行简单的理解:将某一段区间的元素映射到
顺序表中的一个表单元,这里的表单元即桶。这样进行处理以后,可以大幅减少计数排序中桶的数量 。
5 快速排序:分多种情况。有刚好是中间值,有刚好是最大值或最小值,所以时间复杂度是不固定的。
核心原理:分而治之+递归思想。(在冒泡排序的思想上进行演变的)
6 堆排序:可以优化求第n大值的算法。可以先取出n个值构造一个堆,再与堆顶比较,
不满足时,就ch
满二叉树:每个节点都有两个子节点,除了叶子节点。
完全二叉树:每一层的子节点都满了,最后一层的叶子节点集中在左边。
7 二分查找
对有序的列表进行对半查找,从而减少查找的次数,提高查找性能。
8 Tire:单词查找树
同是树结构,通过公共前缀可以提升查找性能。减少同类字符串的比较查找。
9 B+树:非线性查找
有索引可以提升查找性能,但影响写入和更新性能,因为索引变更要移动结构
