5 - 基础知识

5.1 - 五大常用算法

5.1.1 分治法

5.1.2 动态规划

5.1.3 贪心

5.1.4 回溯

5.1.5 分支限界

软件开发

排序

排序算法	平均时间	最差情况	稳定程度	额外空间	备注
冒泡排序	$O(n^2)$	$O(n^2)$	稳定	$O(1)$
交换排序	$O(n^2)$	$O(n^2)$	不稳定	$O(1)$
选择排序	$O(n^2)$	$O(n^2)$	不稳定	$O(1)$
插入排序	$O(n^2)$	$O(n^2)$	稳定	$O(1)$
快速排序	$O(nlog(n))$	$O(n^2)$	不稳定	$O(nlog(n))$
希尔排序	$O(log_2(n))$	单元格	单元格	单元格
归并排序	单元格	单元格	单元格	单元格
堆排序	单元格	单元格	单元格	单元格
基数排序	单元格	单元格	单元格	单元格

快速排序

插入排序

查找

哈希查找（hash，散列表）

定义：

负载因子：散列表的一个重要参数是负载因子a

a = 散列表中结点的数目/基本区域能容纳的结点数。

常用的数据结构框架

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合的合并与查询问题。