【数据库系统工程师】3.4常用算法

目录

• 一、思维导图
• 二、知识点
• • 1.算法概述
  • • （1）算法的基本概念
    • （2）算法与数据结构
    • （3）算法的描述
    • （4）算法的效率
  • 2.排序
  • • （1）简单排序
    • （2）希尔排序
    • （3）快速排序
    • （4）堆排序
    • （5）归并排序
    • （6）各种方法比较
    • （7）外部排序
  • 3.查找
  • • （1）查找表及查找效率
    • （2）顺序查找
    • （3）折半查找
    • （4）索引顺序查找
    • （5）树表查找
    • （6）哈希查找
  • 4.递归算法
  • 5.图的相关算法
  • • （1）求最小生成树算法
    • （2）拓扑排序
    • （3）求单源点的最短路径算法

---

一、思维导图

二、知识点 1.算法概述 （1）算法的基本概念

○ 特性
■ 有穷性
■ 确定性
■ 可行性
■ 输入
■ 输出
○ 优劣考查
■ 正确性
■ 可读性
■ 健壮性
■ 效率

（2）算法与数据结构

○ 算法实现时总是建立在一定的数据结构基础上

（3）算法的描述

○ 流程图
○ N/S盒图
■ 基本元素和控制结构

■ 示例

○ 决策表

（4）算法的效率

解决同一个问题总是存在多种算法，每个算法在计算机上执行时，都要消耗时间(CPU执
行指令的时间)和使用存储空间资源。因此，设计算法时需要考虑算法运行时所花费的时间和
使用的空间，以时间复杂度和空间复杂度表示。.

2.排序 （1）简单排序

○ 直接插入排序
■ 稳定排序，时间复杂度O(n2)，空间复杂度O(1)
○ 冒泡排序
■ 稳定排序，时间复杂度O(n2)，空间复杂度O(1)
○ 简单选择排序
■ 不稳定排序，时间复杂度O(n2)，空间复杂度O(1)

（2）希尔排序

○ 又称缩小增量排序，不稳定排序

（3）快速排序

○ 不稳定排序，时间复杂度O(nlog2n)

（4）堆排序

○ 不稳定排序，时间复杂度O(nlog2n)，空间复杂度O(1)

（5）归并排序

○ 稳定排序，时间复杂度O(nlog2n)，空间复杂度O(n)

（6）各种方法比较

（7）外部排序

○ 对大型文件的排序，待排序的记录存放在外存

3.查找 （1）查找表及查找效率

○ 静态查找表
○ 动态查找表
○ 关键字
○ 查找
○ 平均查找长度

（2）顺序查找 （3）折半查找 （4）索引顺序查找 （5）树表查找 （6）哈希查找

○ 哈希造表
○ 处理冲突
■ 开放定址法
■ 链地址法
○ 哈希查找

4.递归算法

递归(recursion) 是一种描述和解决问题的基本方法，用来解决可归纳描述的问题，或者 是可分解为结构自相似的问题。所谓结构自相似，是指构成问题的部分与问题本身在结构上相 似。这类问题具有的特点是:整个问题的解决可以分为两部分，第一部分是–些特殊或基本的 情况，可直接解决;第二部分与原问题相似，可用类似的方法解决，但比原问题的规模小。.

5.图的相关算法 （1）求最小生成树算法

○ 生成树的概念

○ 最小生成树
■ 普里姆(Prim)算法
■ 克鲁斯卡尔(Kruskal)算法

（2）拓扑排序

○ AOV网
○ 拓扑排序

（3）求单源点的最短路径算法