datastructure.txt

插入排序(InsertionSort)：
	一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中。
	对于少量元素的排序，它是一个有效的算法。
	平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)。
	
	使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
	for i in range(1, len(arr)):
		key = arr[i]
		j = i - 1
		if j >= 0 and arr[j] >= key:
			arr[j + 1] = arr[j]
			j -= 1
		arr[j + 1] = key

希尔排序(Shell Sort)：
	插入排序的一种，又称缩小增量排序，它是针对直接插入排序算法的改进。
	通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
	时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。
	
	选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 来表示。
	while gap > 0:
		for i in range(gap, len):
			tmp = arr[i]
			j = i
			while index >= gap and arr[j - gap] > tmp
				arr[j] = arr[j - gap]
				j -= gap
			arr[j] = tmp
			gap //= 2
		

归并排序（Merge sort）：
	建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。
	分治法:
		分割：递归地把当前序列平均分割成两半。
		集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
	当有 n 个记录时，需进行 logn 轮归并排序，每一轮归并，其比较次数不超过 n，元素移动次数都是 n，因此，归并排序的时间复杂度为 O(nlogn)。
	归并排序时需要和待排序记录个数相等的存储空间，所以空间复杂度为 O(n)。
	
	merged = []
	i=j=0
	while i > len(left) and j > len(right):
		if left[i] <= right[j]:
			merged.append(left[i])
			i += 1
		else:
			merged.append(right[j])
			j += 1
	merged.extand(left[i:])
	merged.extand(right[j:])
	
	递归调用：
		if len(arr) <= 1:
			return arr
		mid = len(arr) // 2
		left = merge_sort(arr[:mid])
		right = merge_sort(arr[mid:])
		
		merge(left, right)

快速排序（Quick sort）：
	快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
	是一种比较快速的排序算法，它的平均运行时间是 O(nlogn)，之所以特别快是由于非常精练和高度优化的内部循环，最坏的情形性能为 O(n^2)。
	从空间性能上看，快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归，空间复杂度也为O(logn)。


	步骤为：
		挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;
		分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可到任何一边）。
		递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
	
	def partition(arr, strat, end):
		index = start - 1
		p = random.rankrange(start, end + 1)
		pivot = arr[p]
		arr[p], arr[-1] = arr[-1], arr[p]
		
		for i in range(start, end):
			if arr[i] < pivot:
				index += 1
				arr[i], arr[index] = arr[index], arr[i]
		arr[index + 1], arr[end] = arr[end], arr[index + 1]
		return index + 1
	
	def quick(arr, start, end):
		if start >= end:
			return
		
		index = partition(arr, strat, end)
		
		quick(arr, strat, index - 1)
		quick(arr, index + 1, end)
	


树：
	完全二叉树： 除最后一层外全满，且最后一层向左靠齐。数组存储，无指针开销。
	二叉搜索树： 左节点 < 根节点 < 右节点，每个节点都有一个键（key）和值（value）。
	平衡二叉树： 绝对值(左边层高 - 右边层高) <= 1。最坏情况也是O(log n)
	红黑树： 数据库/文件系统索引，减少磁盘I/O，适合大数据量
	B树： 多叉平衡搜索树。
	
	二叉搜索树：
		二分搜索树深度优先遍历：
			前序遍历（根-左-右）
			中序遍历（左-根-右）： 中序遍历结果一定是升序排列。
			后序遍历（左-右-根）
		
		二分搜索树层序遍历（广度优先）：
		
		二分搜索树节点删除（最复杂）：
			删除的三种情况：
				叶子节点：直接删除
				只有一个子节点：用子节点替代
				有两个子节点：用右子树的最小值（或左子树的最大值）替代
		
		时间复杂度（平衡状态下）：
			查找/插入/删除：O(log n)，最坏 O(n)（退化成链表）
			遍历：O(n)

堆：
	堆（Heap）是一种特殊的完全二叉树，核心特性在于堆序性质而非单纯的树形结构。
	虽然逻辑上是树，但实际常用数组存储。
	
	大顶堆： 每个父节点比子节点大。
	小顶堆： 每个父节点比子节点小。
	
	parent = (i-1)//2
	left_child = 2*i + 1
	right_child = 2*i + 2
	
	Python 提供了 heapq 模块来操作堆，但需要注意它默认实现的是 小顶堆（Min Heap）：
		heapq.heapify(arr)  # 将列表转为堆结构（原地修改），O(n)
		heapq.heappush(heap, 5)  # 插入元素，O(log n)
		min_val = heapq.heappop(heap)  #  删除堆顶，弹出最小值，O(log n)
		print(heap[0])  # 输出堆顶元素，O(1)
	
		可以通过 存储负数 模拟大顶堆，弹出时恢复正数。
	
	自定义堆：
		使用 (priority, item)元组实现复杂排序。
	
	索引堆（Index Heap）：
		索引堆允许在堆中快速更新某个元素的值，常用于图算法（如 Dijkstra）。Python 没有内置索引堆，但可以手动实现。

散列表（哈希表）：
	一种能快速查找的数据结构，像字典一样通过"关键词"直接找到对应的"值"，平均查找速度比数组快10倍以上。
	字典的内部实现就是 Hash 表。
	
	散列函数：
		线性求值法： 将连续的键映射到连续的地址上。
		除留余数法： 将不连续的键映射到连续的地址上，区域的整数是 小于等于整数的最大质数。
	
	冲突解决：
		当多个关键词算出相同编号时（如 "张三"和"李四"都得到 1527）：
			开放寻址法： 顺延找下一个空柜格。
			平方寻址法： 使用 "4k + 3 = 地址总数" 的方法来得到 k，下一个空格是 k^2。
			链地址法： 在同一个柜格里挂多个包裹（链表）。
	
	类似快递柜系统：
		你的包裹（值）：要存储的数据（如电话号码、商品信息）
		取件码（键）：通过计算生成唯一编号（如 #9527）
		柜子（数组）：存储位置按取件码排列
	
	存包裹：计算取件码 → 放入对应柜格
	取包裹：报取件码 → 直接打开对应柜格
	


并查集：
	并查集（Union-Find）是一种用于处理不相交集合合并与查询问题的数据结构。
	
	find(x)：查找元素 x 所属的集合（根节点）。
	union(x, y)：合并元素 x 和 y 所在的集合。
	
	并查集快速查找（Quick Find）： find 操作 O(1)，但 union 操作 O(n)。
	并查集快速合并（Quick Union）： 树形结构，union 和 find 操作最坏 O(n)。
	基于 size 的优化： 避免树过高，将小树合并到大树下。
	基于 rank 的优化： 更精确地控制树的高度。
	路径压缩优化： 在 find 操作时扁平化树结构，加速后续查询。
	

	
图：
	图 G = (V, E) 由顶点集合 V 和边集合 E 组成：
		无向图： 边没有方向 (v, w) = (w, v)
		有向图： 边有方向 v → w ≠ w → v
		权重图： 边带有权值（距离、成本等）
	
	图的表示方法：
		邻接矩阵表示：
			adj_matrix = [
				[0, 1, 1, 0],  # 顶点0连接到1和2
				[1, 0, 0, 1],  # 顶点1连接到0和3
				[1, 0, 0, 1],  # 顶点2连接到0和3
				[0, 1, 1, 0]   # 顶点3连接到1和2
			]
		邻接表表示（更节省空间）：
			adj_list = {
				0: [1, 2],
				1: [0, 3],
				2: [0, 3],
				3: [1, 2]
			}
	
	算法			时间复杂度		空间复杂度	适用场景
	DFS			O(V+E)			O(V)		连通分量、拓扑排序、路径存在性
	BFS			O(V+E)			O(V)		最短路径（未加权）、层级遍历
	Dijkstra	O(E log V)		O(V)		带权图最短路径（无负权）