数据结构与排序算法概述

线性数据结构

• 定义: 数据元素按顺序排列，每个元素只有一个前驱和一个后继。
• 主要类型:
  • 数组: 固定大小，快速随机访问，但插入和删除效率低。
  • 链表: 动态大小，易于插入和删除，但随机访问效率低。
    • 单链表: 每个节点指向下一个节点。
    • 双链表: 每个节点指向前后两个节点。
    • 循环链表: 链表的最后一个节点指向第一个节点。
  • 栈: 后进先出（LIFO），主要操作是压入和弹出。
  • 队列: 先进先出（FIFO），主要操作是入队和出队。

非线性数据结构

• 定义: 数据元素之间不是线性关系，结构更复杂。
• 主要类型:
  • 树: 层次结构，每个节点可有多个子节点。
    • 二叉树: 每个节点最多两个子节点。
    • 平衡树: 保持树的高度平衡，提升搜索效率（如AVL树、红黑树）。
    • 堆: 完全二叉树，满足堆性质（如最大堆、最小堆）。
  • 图: 由节点（顶点）和边（连接）组成，可表示复杂关系。
    • 有向图: 边有方向。
    • 无向图: 边无方向。
    • 加权图: 边带权重。

排序算法

• 定义: 将一组数据按特定顺序排列。
• 常见排序算法:
  • 冒泡排序: 简单，重复比较相邻元素，时间复杂度O(n²)。
  • 选择排序: 每次选择最小元素并放到前面，时间复杂度O(n²)。
  • 插入排序: 将元素插入到已排序部分，时间复杂度O(n²)。
  • 归并排序: 分治法，递归地分割和合并，时间复杂度O(n log n)。
  • 快速排序: 选择“基准”元素，分割并排序，平均时间复杂度O(n log n)。
  • 堆排序: 利用堆结构进行排序，时间复杂度O(n log n)。

搜索算法

• 定义: 在数据结构中查找特定元素。
• 常见搜索算法:
  • 线性搜索: 从头到尾依次检查，时间复杂度O(n)。
  • 二分搜索: 在已排序数组中查找，通过折半降低查找范围，时间复杂度O(log n)。
  • 深度优先搜索（DFS）: 在图或树中优先探索尽可能深的分支。
  • 广度优先搜索（BFS）: 在图或树中逐层探索邻近节点。

算法复杂度

• 定义: 衡量算法性能，主要包括时间复杂度和空间复杂度。
• 时间复杂度:
  • 表示算法执行时间随输入规模增长的变化。
  • 常用符号:
    • O(1): 常数时间
    • O(log n): 对数时间
    • O(n): 线性时间
    • O(n log n): 线性对数时间
    • O(n²): 平方时间
• 空间复杂度:
  • 表示算法所需的额外空间随输入规模增长的变化。
  • 重要性: 确保在资源有限的环境下算法的有效性。

线性数据结构

• 数据元素按顺序排列，每个元素有唯一的前驱和后继。
• 数组: 数据固定大小，支持快速随机访问，插入和删除效率低。
• 链表: 动态大小，可高效插入和删除，随机访问效率较低。
  • 单链表: 节点仅指向下一个节点。
  • 双链表: 节点指向前后两个节点。
  • 循环链表: 最后一个节点指向第一个节点，形成循环。
• 栈: 遵循后进先出（LIFO）原则，主要操作包括压入和弹出。
• 队列: 遵循先进先出（FIFO）原则，主要操作为入队（enqueue）和出队（dequeue）。

非线性数据结构

• 数据元素之间关系复杂，非线性排列。
• 树: 具层次结构，节点可有多个子节点。
  • 二叉树: 每个节点最多有两个子节点。
  • 平衡树: 保持树的高度平衡，提高搜索效率（如AVL树、红黑树）。
  • 堆: 完全二叉树，满足特定堆性质（如最大堆、最小堆）。
• 图: 由节点（顶点）和边（连接）组成，用于表达复杂关系。
  • 有向图: 边有方向。
  • 无向图: 边无方向。
  • 加权图: 边有权重，常用于表示成本或距离。

排序算法

• 用于将数据按特定顺序排列。
• 冒泡排序: 持续比较相邻元素，时间复杂度为O(n²)。
• 选择排序: 从未排序部分选择最小元素放到前面，时间复杂度为O(n²)。
• 插入排序: 将元素插入至已排序部分，时间复杂度为O(n²)。
• 归并排序: 采用分治法进行分割与合并，时间复杂度为O(n log n)。
• 快速排序: 选择基准元素进行分割和排序，平均时间复杂度为O(n log n)。
• 堆排序: 通过堆结构进行排序，时间复杂度为O(n log n)。

搜索算法

• 用于查找数据结构中的特定元素。
• 线性搜索: 顺序检查每个元素，时间复杂度为O(n)。
• 二分搜索: 在已排序数组中，通过折半查找降低查找范围，时间复杂度为O(log n)。
• 深度优先搜索（DFS）: 优先探索尽可能深的分支，适用于图或树。
• 广度优先搜索（BFS）: 按层次探查邻近节点，适用于图或树。

算法复杂度

• 衡量算法性能的指标，包含时间复杂度和空间复杂度。
• 时间复杂度: 反映算法执行时间与输入规模的关系，用符号表示。
  • O(1): 常数时间。
  • O(log n): 对数时间。
  • O(n): 线性时间。
  • O(n log n): 线性对数时间。
  • O(n²): 平方时间。
• 空间复杂度: 描述算法所需的额外空间随输入规模的变化，确保算法在资源有限环境下的有效性。