# 软考-软件设计师-7-数据结构与算法

# 主要概念

哈希冲突时，冲突的 key 称为同义词

队列空或满不是由数据结构决定的

矩阵压缩方法：三元组顺序表、行逻辑连接的顺序表、十字链表

要点：按间隔进行分组，组内使用直接插入排序，间隔每次减半，间隔为 1 时做最后一次组内直接插入排序

希尔排序的目的是：减少比较次数与交换次数，所以最差的时间复杂的是 O(n^1.3)

与快速排序相比，希尔排序的空间复杂度比较高，每次都要分配新的数组

要点：基准值（挖坑），头尾指针与跟基准值比较并填坑，头尾指针相遇时完成一轮排序

golang 使用快速排序作为基础算法

快速排序的时间复杂度（平均）、空间复杂度都很好

排序算法	最好时间复杂度	最坏时间复杂度	稳定性
直接插入	`O(n)`	`O(n^2)`	稳定
简单选择	`O(n^2)`	`O(n^2)`	不稳定
冒泡排序	`O(n)`	`O(n^2)`	稳定
希尔排序	`O(n)`	`O(n^1.3)`	不稳定
快速排序	`O(nlogn)`	`O(n^2)`	不稳定
堆排序	`O(nlogn)`	`O(nlogn`)	不稳定
归并排序	`O(nlogn)`	`O(nlogn`)	稳定

字符	a	b	c	d	e
频率 %	40	10	20	16	14

a: 0
b: 100
c: 111
d: 110
e: 101

cade: 1110110101

压缩后长度=1*0.4+3*0.1+3*0.2+3*0.16+3*0.14=2.2
压缩率=(3-2.2)/3=27%