- 查找
- 顺序查找
- 二分查找
- Hash查找
- 分组求合法
- 平方取中法
- 排序
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
Tech
顺序查找
- 无序列表和有序列表都是 O(n)
二分查找
- 有序列表对于二分查找非常重要
- 选择中间的数进行比较,然后缩小范围,在选择中间数进行比较
- O(log^n)
Hash查找
- 开地址法和拉链法
冒泡排序
- 将列表从头开始遍历,每次遍历都将最大的值放在正确的地方(比如列表的尾部)
- 一共要循环n-1次,所以复杂度是 O(n^2)
- 若遍历期间没有交换,则说明已经排序,若已经排序,则可以提前停止。这种叫 短冒泡排序
选择排序
- 每次遍历记录下最大的项,只做一次交换
- 虽然也是O(n^2) 但是交换次数明显减少很多
插入排序
- 维护一个子列表, 每次遍历都将新值插入到合适的位置
- 新值和列表中的末尾进行比较,若末尾大,则后移一位,继续比较。直到遇到小于他的数字,则停止移位,并停留在空白处。
希尔排序
- 递减递增排序
- 将原始列表拆分为多个子列表
- 每个子列表采用插入排序
- 选取合适的增量GAP来决定子列表
归并排序
- 不断将列表拆分为一半,若列表为空或一半,则按定义进行排序
- 一旦对两半列表排序完成,则进行合并
快速排序
- 选择一个枢轴值,帮助拆分列表。一般选择第一个。
- 从左开始直到大于枢轴值,从右开始直到小于枢轴值,交换2个值,继续。
- 若枢轴值在中间,则只需要O(log^n),为了找到分割点,需要检查n个项,所以是O(nlog^n),如果非常偏向左或右,就是O(n)