各种排序查询的算法效率比较
各种排序查询的算法效率比较
一 排序
|
SN |
排序方式 |
时间复杂度 |
空间复杂度 |
稳定性 |
算法描述 |
||
备注:
时间复杂度O(1)<O(n)<O(logn)<O(nlogn)<O(n2)
1,2,3属于插入排序; 4,5属于交换排序; 6,7属于选择排序.
记录数大时,选择改进算法; 记录数较小时,可采用简单排序(如1,4,6)
平均情况下,快速排序速度是最快的,推荐使用.
稳定性指具有相同值的记录在排序时相对次序不改变.
内排序: 数据量较少时,仅在内存中进行;
外排序: 数据量较大时,在内外存中进行数据交换(常用归并排序,文件来解决)
二 查询
检索表: 检索所依赖的数据结构.
查询定义: 根据KEY,在检索表中确定VALUE的值.
1 线性表
1)顺序检索: 采用逆向检索
2)折半检索
3)分块检索
2 树表
1)二叉排序树
2)平衡的二叉排序树
3)B树
4)红黑树
3 HASH表
最快只需常数时间.
4 其它数据结构
1)序列容器
VectOr: 类似线性表
List 类似线性表
2)关联容器
Map: 图的检索, 一对一
Multimap: 一对多
Hashmap: 常数时间检索,用hash_table实现.
检索算法评估: (平均检索长度ASL)
下面是检索算法效率列表:
|
检索表 |
检索算法 |
ASL |
算法描述 |
|
线性表 |
顺序 |
(n+1)/2 |
|
|
折半 |
Log2(n+1)-1 (n>>100) |
适用于有序表 |
|
|
分块 |
|||
|
树表 |
二叉排序树 |
||
|
平衡二叉排序树 |
|||
|
B树 |
|||
|
红黑树 |
|||
|
HASH表 |
|||
没有评论▼