数据结构

# 数据结构与算法分析

# 排序算法

排序算法是最常用的算法之一，它用于对数据集合进行排列。这里将介绍一些常见的排序算法：冒泡排序、快速排序、归并排序、插入排序、选择排序和堆排序。

# 1. 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法，它通过重复交换相邻未按顺序排列的元素，直到整个序列按顺序排列。每一轮操作将最大元素“冒泡”到最后。

时间复杂度：

最坏和平均时间复杂度为 O(n²)，最好的情况下为 O(n)（当数组已经排序时）。

空间复杂度：

O(1)，只需要常数空间。

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j] 和 arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 2. 插入排序 (Insertion Sort)

插入排序将每个元素插入到已排序的部分，逐步形成一个完整的排序序列。

时间复杂度：

最坏和平均时间复杂度为 O(n²)，最好的情况下为 O(n)（当数组已经排序时）。

空间复杂度：

O(1)，只需要常数空间。

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 3. 选择排序 (Selection Sort)

选择排序每次从未排序的部分中选择最小元素，放到已排序部分的末尾。

时间复杂度：

O(n²)，无论输入数据是否有序。

空间复杂度：

O(1)，只需要常数空间。

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // 交换元素
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 4. 快速排序 (Quick Sort)

快速排序采用分治法，将数组分为较小的部分进行排序，最终合并。它选择一个“基准”元素，将大于基准的元素移到右边，小于基准的元素移到左边，然后递归对这两部分继续排序。

时间复杂度：

最坏时间复杂度为 O(n²)，最好的情况下为 O(n log n)。

空间复杂度：

O(log n)，栈的深度。

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 5. 归并排序 (Merge Sort)

归并排序也是一种分治法排序算法，它将数组分成两个子数组，分别排序后合并。它具有稳定性，适合大规模数据排序。

时间复杂度：

O(n log n)，不受输入数据的影响。

空间复杂度：

O(n)，需要额外的空间来存储中间数组。

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        System.arraycopy(arr, left, L, 0, n1);
        System.arraycopy(arr, mid + 1, R, 0, n2);

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 6. 堆排序 (Heap Sort)

堆排序基于完全二叉树的堆结构。它将数组视为一个二叉堆，最大堆或最小堆，然后通过反复移除根节点来构建排序序列。

时间复杂度：

O(n log n)，无论输入数据是否有序。

空间复杂度：

O(1)，只需要常数空间。

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 一次次移除根节点，调整堆
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 树结构

树结构广泛应用于搜索、排序和分层数据存储等领域。常见的树包括完全二叉树、前缀树、二叉搜索树、AVL 树和红黑树。

# 1. 完全二叉树 (Complete Binary Tree)

完全二叉树是一种特殊的二叉树，具有以下核心特点：

层级填充：除了可能最后一层外，所有层都必须填满节点。
靠左排列：最后一层的节点必须从左到右依次排列，不能有空隙。

换句话说，它是一棵“几乎满”的二叉树，最后一层可以不满，但节点必须集中在左侧。

基本性质

高度：如果树高为 $h$ ，前 $h - 1$ 层是满的，每层有 $2^{i}$ 个节点（ $i$ 是层号）。
节点数：范围在 $2^{h}$ 到 $2^{h + 1} - 1$ 之间。
存储方式：可以用数组表示，节点按层序排列，方便访问子节点和父节点。

# 2. 前缀树 (Trie)

前缀树，又称 字典树 或 Trie 树，是一种专门用于处理字符串的树形数据结构。它的核心思想是通过共享前缀来高效存储和检索一组字符串。

基本概念

节点结构：
- 每个节点代表一个字符。
- 从根节点到某个节点的路径表示一个字符串的前缀。
- 根节点通常是空的（不代表任何字符）。
特点：
- 共享前缀：具有相同前缀的字符串共享路径上的节点，从而节省存储空间。
- 叶子节点或标记：通常用一个特殊标记（比如布尔值 isEnd）表示从根到该节点是否构成一个完整的单词。
用途：
- 快速查找某个字符串是否存在。
- 检索具有特定前缀的所有字符串（前缀查询）。
- 常用于自动补全、拼写检查、字典实现等。

简单例子

假设要存储字符串 "cat"、"car" 和 "dog"：

       (根)
      / | \
     c  d  ...
    /   |
   a    o
  / \   |
 t   r  g

1
2
3
4
5
6
7

路径 c -> a -> t 表示 "cat"。
路径 c -> a -> r 表示 "car"。
路径 d -> o -> g 表示 "dog"。
"ca" 是 "cat" 和 "car" 的共享前缀。

# 3. 二叉搜索树 (BST)

**二叉搜索树（Binary Search Tree, BST）**是一种特殊的二叉树，每个节点的值大于左子树所有值，小于右子树所有值。它支持高效的搜索、插入、删除，时间复杂度取决于树高 $O (h)$ 。中序遍历会得到递增序列，但如果不平衡（比如递增插入 1, 2, 3），会退化成链表，效率变低。可以用平衡树（如 AVL 或红黑树）改进。

简单例子

假设有一棵 BST：

1
2
3
4
5

根节点是 5。
左子树 (3, 1, 4) 都小于 5。
右子树 (7, 8) 都大于 5。
中序遍历结果：1, 3, 4, 5, 7, 8（递增顺序）。

基本操作

搜索：
- 从根开始，若目标值小于当前节点值，去左子树；若大于，去右子树；相等则找到。
- 时间复杂度： $O (h)$ ， $h$ 是树高。
插入：
- 类似搜索，找到合适位置插入新节点。
- 时间复杂度： $O (h)$ 。
删除：
- 删除节点时需调整树结构（分情况：无子节点、一个子节点、两个子节点）。
- 时间复杂度： $O (h)$ 。

# 4. AVL 树

AVL 树是一种自平衡的二叉搜索树，确保任意节点的左右子树高度差（平衡因子）不超过 1，从而在最坏情况下也能保持 O(log n) 的时间复杂度。

时间复杂度：

查找操作： 由于树的高度被限制在 O(log n)，查找操作的时间复杂度为 O(log n)。
插入和删除操作：在最坏情况下，插入和删除操作需要进行旋转调整，以维持树的平衡，时间复杂度仍为 O(log n)。

空间复杂度：

AVL 树的空间复杂度为 O(n)，其中 n 是树中节点的数量。

# 5. 红黑树

红黑树是一种自平衡的二叉搜索树，每个节点带有红色或黑色属性，通过五条规则保持平衡：根节点为黑色、叶子（NIL）为黑色、红色节点的子节点必须为黑色、从根到叶子的每条路径黑色节点数相同、节点非红即黑。这些规则确保树高最多为 $O (\log n)$ ，提供高效操作。插入或删除时，通过颜色调整和旋转维持平衡，相比 AVL 树调整更灵活。

时间复杂度：

查找操作： 由于树高被限制在 $O (\log n)$ ，查找操作的时间复杂度为 $O (\log n)$ 。
插入和删除操作： 在最坏情况下，插入和删除需要颜色调整和旋转以维持平衡，时间复杂度仍为 $O (\log n)$ 。

空间复杂度：

红黑树的空间复杂度为 $O (n)$ ，其中 $n$ 是树中节点的数量。

# 6. B 树与 B+ 树

B树和B+树是两种高效的多路平衡搜索树，广泛应用于数据库和文件系统中，用于管理大量数据并优化磁盘访问。以下是它们的核心特点和对比：

# 1. B树（B-Tree）

特点：

多路平衡：每个节点最多有 m 个子节点（m 阶B树），且所有叶子节点在同一层。
键值分布：每个节点包含多个键（k 个）和子节点指针（k+1 个），键按升序排列，子节点键值范围由其父节点键分割。
数据存储：所有节点都可能存储数据（键关联实际数据或指针）。

优势：

减少磁盘I/O：矮胖的树形结构降低树的高度，减少磁盘访问次数。
平衡性：插入、删除时通过分裂、合并节点自动维持平衡。
适用场景：适合读写操作混合且数据量大的场景，如文件系统（NTFS、ReiserFS）。

示例：

# 2. B+树（B+ Tree）

特点：

数据仅存于叶子：内部节点仅存储键和子节点指针，所有数据记录集中在叶子节点。
叶子链表：叶子节点通过指针形成有序链表，支持高效的范围查询。
键冗余：内部节点的键会在叶子节点中重复出现（作为子树的最大/最小值）。

优势：

更稳定的查询：任何查询都需到叶子节点，时间复杂度一致。
高效范围查询：链表结构直接遍历叶子节点即可，无需回溯树。
更优的磁盘I/O：内部节点可存储更多键，进一步降低树的高度。
适用场景：数据库索引（如MySQL InnoDB），强调范围查询和顺序访问。

示例：

# 3. 对比

特性	B树	B+树
数据存储位置	所有节点均可存数据	仅叶子节点存储数据
叶子节点结构	独立，无链表连接	通过指针形成有序链表
查询稳定性	可能在内部节点命中，时间不固定	必须到叶子节点，时间稳定
范围查询效率	低效（需中序遍历）	高效（直接遍历叶子链表）
空间利用率	内部节点存储数据，占用更多空间	内部节点仅存键，空间利用率更高
适用场景	文件系统、特定数据库（MongoDB）	关系型数据库（MySQL）、大数据索引

编辑

上次更新: 2025/04/01, 01:48:12

← Redis 云计算→