数据结构算法高频总结一

发表于 2025/01/13 更新于 2025/01/13

作者 匆匆那年 29 分钟阅读

数组和链表区别和优缺点

数组和链表是两种常见的数据结构，它们各有特点、优缺点和适用场景。

数组的特点

连续存储：数组在内存中占用一块连续的空间。
固定大小：数组在定义时需要指定大小，不能动态扩展（静态数组）。
随机访问：数组支持通过索引直接访问任意元素，时间复杂度为 O(1)。
元素类型一致：数组中的元素通常是相同的数据类型。

链表的特点

非连续存储：链表中的每个节点通过指针链接，节点可以存储在内存的任意位置。
动态大小：链表的长度可以根据需求动态增加或减少。
线性访问：链表只能从头节点逐一遍历到目标节点，时间复杂度为 O(n)。
节点包含指针：每个节点不仅存储数据，还包含指向下一个节点的指针（或前后节点的指针，视链表类型而定）。

数组的优点

快速随机访问：支持通过索引直接访问任意元素，效率高。
内存利用率高：数据紧密排列，没有额外的指针开销。
缓存友好：由于内存连续存储，访问时可利用 CPU 缓存提高效率。

数组的缺点

固定大小：无法动态调整长度（除非使用动态数组，如 C++ 的 std::vector ）。
插入和删除效率低：需要移动大量元素，时间复杂度为 O(n)。
内存空间浪费：如果数组大小设置过大而实际使用不足，会浪费内存。

链表的优点

动态调整大小：链表可以根据需要灵活地增加或删除节点。
高效的插入和删除：在已知位置插入或删除元素，时间复杂度为 O(1)。
内存利用率灵活：节点分散存储，减少了因连续空间不足导致的内存浪费。

链表的缺点

访问效率低：只能从头节点依次遍历到目标节点，时间复杂度为 O(n)。
内存开销大：每个节点需要额外的指针存储，增加了内存消耗。
不缓存友好：节点分散存储，访问时无法充分利用 CPU 缓存。

适用场景

场景	选择数组	选择链表
数据大小固定，随机访问频繁	✅	❌
数据大小不固定，频繁插入/删除操作	❌	✅
内存连续性和缓存性能要求高	✅	❌
节约内存，不需要额外指针存储空间	✅	❌

总结

数组适合于数据大小固定且访问频繁的场景，比如实现栈、队列或需要快速索引的场景。
链表适合于数据大小不确定且需要频繁插入、删除操作的场景，比如动态集合、图的邻接表表示等。

选择数组还是链表，需要结合具体应用场景的需求来权衡性能与内存开销。

快速排序

快速排序（QuickSort）是一种高效的分治算法，用于对数组或列表进行排序。它的基本思想是通过选择一个“基准值（pivot）”，将数据分成两部分，一部分比基准值小，另一部分比基准值大，然后对这两部分分别递归地进行快速排序。

快速排序算法步骤

选择基准值：
- 通常选择数组的第一个元素、最后一个元素、或中间的元素作为基准值，也可以随机选择。
分区（Partition）：
- 将小于基准值的元素放在基准值的左边，大于基准值的元素放在右边。
- 基准值归位后，左右两部分分别成为一个子问题。
递归排序：
- 对基准值左边和右边的子数组分别进行快速排序。
合并：
- 快速排序本身是原地排序，不需要额外合并步骤，排序完成后数组已经有序。

快速排序的代码实现（C++ 示例）

  
#include <iostream>
#include <vector>

void quickSort(std::vector<int>& arr, int low, int high);
int partition(std::vector<int>& arr, int low, int high);

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // 获取分区索引
        int pivotIndex = partition(arr, low, high);
        // 递归对左子数组排序
        quickSort(arr, low, pivotIndex - 1);
        // 递归对右子数组排序
        quickSort(arr, pivotIndex + 1, high);
    }
}

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1;       // i 指向小于基准值的区域末尾

    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]); // 交换使得较小的元素靠左
        }
    }
    std::swap(arr[i + 1], arr[high]); // 将基准值放到正确位置
    return i + 1;                     // 返回基准值位置
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    quickSort(arr, 0, n - 1);

    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

快速排序的时间复杂度

最优时间复杂度：
$O(n \log n)$
- 每次分区都均匀地将数组分成两部分。
最差时间复杂度：
$O(n^2)$
- 每次分区非常不均匀，例如选择最小或最大值作为基准（退化为冒泡排序）。
平均时间复杂度：$O(n \log n)$

快速排序的空间复杂度

空间复杂度：$O(\log n)$（递归调用栈）
快速排序是原地排序算法，不需要额外的辅助存储空间。

快速排序的优缺点

优点

时间复杂度在实际应用中表现非常优秀，平均复杂度低。
原地排序，无需额外空间。
可用于大多数场景，适合处理大规模数据。

缺点

最差情况下的时间复杂度较高（$O(n^2)$）。
对于小数组或几乎有序的数组，性能可能不如插入排序。
不稳定排序：同值元素的相对顺序可能被打乱。

优化策略

三数取中法选择基准值：
- 避免在已排序或几乎排序的数组中退化为最差时间复杂度。
尾递归优化：
- 优化递归调用，减少栈空间。
小规模数组使用插入排序：
- 当子数组规模较小时（如 10 个元素以下），改用插入排序更高效。

总结

快速排序是高效的分治算法，适用于大多数场景。
在C++中，直接使用std::sort也可以达到快速排序的效果，其内部实现通常包含快速排序、插入排序和堆排序的混合优化版本，性能更优。

堆排序是怎么做的

堆排序（Heap Sort）是一种基于堆数据结构的排序算法，属于选择排序的一种。它通过将数组构造成一个最大堆或最小堆，然后依次取出堆顶元素（最大或最小）来实现排序。

堆排序的基本原理

构建初始堆：
- 将待排序数组调整为最大堆（升序排序）或最小堆（降序排序），堆的根节点为最大值或最小值。
交换堆顶与末尾元素：
- 将堆顶元素与当前堆的最后一个元素交换，使堆顶元素归位。
调整堆结构：
- 交换后，重新调整剩余的元素为最大堆或最小堆。
重复步骤 2 和 3：
- 直到堆中只剩下一个元素，排序完成。

堆排序的代码实现（C++ 示例）

以下是一个基于最大堆实现的升序排序示例：

  
#include <iostream>
#include <vector>

// 调整堆，使其满足最大堆性质
void heapify(std::vector<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) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest); // 递归调整子堆
    }
}

// 堆排序主函数
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

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

    // 逐步将堆顶元素移到数组末尾，并重新调整堆
    for (int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]); // 将堆顶元素移到末尾
        heapify(arr, i, 0);        // 调整剩余元素为最大堆
    }
}

// 测试堆排序
int main() {
    std::vector<int> arr = {10, 15, 20, 3, 5, 8, 1};

    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    heapSort(arr);

    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码说明

heapify 函数：
- 用于调整数组中以 i 为根节点的子树，确保满足最大堆性质。
- 如果左右子节点比根节点大，则交换根节点和较大的子节点，然后递归调整。
heapSort 函数：
- 首先通过从最后一个非叶子节点到根节点的调整过程，将数组构建为最大堆。
- 然后逐步将堆顶元素移到数组末尾，并调整剩余的堆为最大堆。
main 函数：
- 定义测试数组，调用 heapSort 对其排序，并打印结果。

堆排序的时间复杂度

构建堆的时间复杂度：$O(n)$
- 每个节点的调整代价是其高度，累加起来总复杂度为$O(n)$。
调整堆的时间复杂度：$O(n \log n)$
- 在排序过程中需要$n - 1$次调整，每次调整的代价是 $O(\log n)$。
总时间复杂度：$O(n \log n)$

堆排序的空间复杂度

空间复杂度：
$O(1)$
- 堆排序是原地排序算法，无需额外空间。

堆排序的优缺点

优点：

时间复杂度稳定为$O(n \log n)$，不受数据分布影响。
原地排序，不需要额外存储空间。

缺点：

不稳定排序：相同值的元素相对顺序可能被改变。
构建和调整堆的过程相比快速排序，常数因子较大，实际运行时间可能略慢。

堆排序与快速排序的比较

特性	快速排序	堆排序
时间复杂度（平均）	$O(n \log n)$	$O(n \log n)$
时间复杂度（最差）	$O(n^2)$	$O(n \log n)$
空间复杂度	$O(\log n)$（递归栈）	$O(1)$
稳定性	不稳定	不稳定
实际性能	通常更快（常数因子小）	常数因子较大，稍慢

总结

堆排序是一种时间复杂度稳定、适合内存紧张场景的排序算法。尽管在实际应用中其性能通常不如快速排序，但由于其时间复杂度的稳定性和低空间占用，它在某些特定场景（如嵌入式系统）中非常有用。

冒泡排序

冒泡排序（Bubble Sort） 是一种简单直观的排序算法，通过多次遍历数组，每次比较相邻的两个元素，将较大的元素逐步“冒泡”到数组的末尾，从而完成排序。

冒泡排序的基本原理

从头到尾遍历数组：
- 比较相邻的两个元素，如果顺序不正确（如升序排序中前面的元素大于后面的元素），则交换它们。
重复步骤 1：
- 每一轮遍历后，最大的元素会“冒泡”到当前未排序部分的最后。
减少比较范围：
- 每轮排序后，最后一个元素已经是有序的，因此下一轮遍历时可以少比较一个元素。
提前终止优化：
- 如果在某一轮中没有发生任何交换，说明数组已经有序，可以提前结束排序。

冒泡排序的代码实现（C++ 示例）

  
#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false; // 标志位，用于检测是否发生了交换
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]); // 交换相邻元素
                swapped = true;
            }
        }
        // 如果没有发生交换，说明数组已经有序，可以提前结束
        if (!swapped) break;
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};

    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    bubbleSort(arr);

    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码说明

for 循环嵌套：
- 外层循环控制排序的轮次，总共需要 $n - 1$ 轮。
- 内层循环比较相邻元素，并将较大的元素交换到右侧。
优化：标志位 swapped：
- 如果一轮遍历中没有发生任何交换，说明数组已经有序，可以提前结束排序。
性能特点：
- 每轮比较范围缩小，因为最大的元素已经归位。

冒泡排序的时间复杂度

最优时间复杂度：$O(n)$
- 当数组已经有序时，只需一轮遍历即可完成排序。
最差时间复杂度：$O(n^2)$
- 当数组是完全逆序时，需要 $n(n-1)/2 $次比较。
平均时间复杂度：$O(n^2)$

冒泡排序的空间复杂度

空间复杂度：
$O(1)$
- 冒泡排序是原地排序算法，只需常数级的额外空间。

冒泡排序的优缺点

优点：

实现简单，代码直观易懂。
是稳定排序：相等的元素在排序后保持相对位置不变。
对于已经部分有序的数组，性能较好（通过标志位优化）。

缺点：

效率低：即使是优化后的冒泡排序，性能也不如插入排序或选择排序。
不适合大规模数据排序：时间复杂度为 O(n2)O(n^2)，对大数组性能较差。

冒泡排序与其他排序算法的比较

特性	冒泡排序	插入排序	选择排序
时间复杂度（最优）	$O(n)$	$O(n)$	$O(n^2)$
时间复杂度（最差）	$O(n^2)$	$O(n^2)$	$O(n^2)$
空间复杂度	$O(1)$	$O(1)$	$O(1)$
稳定性	稳定	稳定	不稳定

总结

冒泡排序适用于小规模、部分有序的数组，但在实际应用中，性能较低的特点使得它很少用于工业场景。更高效的排序算法，如快速排序、归并排序和堆排序，在大规模数据处理时表现更优。冒泡排序更多用于教学场景或简单任务中。

二分查找

二分查找（Binary Search） 是一种高效的查找算法，用于在有序数组中查找特定的元素。通过每次将查找范围缩小一半，二分查找的时间复杂度仅为 $O(\log n)$。

二分查找的基本原理

前提条件：
- 二分查找要求数组是有序的（升序或降序）。
查找过程：
- 找到数组的中间元素，与目标值比较。
- 如果目标值等于中间元素，则查找成功。
- 如果目标值小于中间元素，则在左半部分继续查找。
- 如果目标值大于中间元素，则在右半部分继续查找。
重复上述过程：
- 每次将查找范围缩小一半，直到找到目标值或查找范围为空。

二分查找的代码实现（C++ 示例）

迭代实现

  
#include <iostream>
#include <vector>
#include <optional>

std::optional<int> binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出

        if (arr[mid] == target) {
            return mid; // 找到目标值，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1; // 在右半部分查找
        } else {
            right = mid - 1; // 在左半部分查找
        }
    }

    return std::nullopt; // 未找到目标值
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;

    auto result = binarySearch(arr, target);

    if (result.has_value()) {
        std::cout << "Element found at index: " << result.value() << std::endl;
    } else {
        std::cout << "Element not found in the array." << std::endl;
    }

    return 0;
}

递归实现

  
#include <iostream>
#include <vector>
#include <optional>

std::optional<int> binarySearchRecursive(const std::vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return std::nullopt; // 未找到目标值
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid; // 找到目标值，返回索引
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right); // 在右半部分查找
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1); // 在左半部分查找
    }
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;

    auto result = binarySearchRecursive(arr, target, 0, arr.size() - 1);

    if (result.has_value()) {
        std::cout << "Element found at index: " << result.value() << std::endl;
    } else {
        std::cout << "Element not found in the array." << std::endl;
    }

    return 0;
}

时间和空间复杂度

时间复杂度：$O(\log n)$
- 每次查找范围缩小一半，最多需要 $\log_2(n) $次比较。
空间复杂度：
- 迭代实现：$O(1)$，只需常量级额外空间。
- 递归实现：$O(\log n)$，递归调用栈的深度为 $\log_2(n)$。

二分查找的优缺点

优点：

时间复杂度低，性能优于线性查找。
实现简单，适合查找有序数据。

缺点：

仅适用于有序数组或其他支持随机访问的数据结构。
数据需要在查找前排序，排序的时间复杂度通常为 $O(n \log n)$。
插入和删除操作成本较高（需要维护数组有序性）。

常见变种

查找第一个等于目标值的元素：
- 在二分查找中，当找到目标值时继续向左查找，直到找到第一个位置。
查找最后一个等于目标值的元素：
- 在二分查找中，当找到目标值时继续向右查找，直到找到最后一个位置。
查找第一个大于或小于目标值的元素：
- 可通过调整二分查找的逻辑实现。

示例：查找第一个大于等于目标值的元素

  
int lowerBound(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size();

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] >= target) {
            right = mid; // 收缩右边界
        } else {
            left = mid + 1; // 收缩左边界
        }
    }

    return left; // 返回第一个大于等于目标值的位置
}

总结

二分查找是一种高效、基础的算法，适合在有序数组中查找元素或解决查找相关问题。通过调整逻辑，可以解决多个变种问题，如上下界查找。实际应用中，可以结合 STL 提供的 std::lower_bound 和 std::upper_bound 方便实现类似功能。

数据结构算法, 数据结构算法面经

数据结构算法面经

本文由作者按照 CC BY 4.0 进行授权

数组和链表区别和优缺点

数组的特点

链表的特点

数组的优点

数组的缺点

链表的优点

链表的缺点

适用场景

总结

快速排序

快速排序算法步骤

快速排序的代码实现（C++ 示例）

快速排序的时间复杂度

快速排序的空间复杂度

快速排序的优缺点

优点

缺点

优化策略

总结

堆排序是怎么做的

堆排序的基本原理

堆排序的代码实现（C++ 示例）

代码说明

堆排序的时间复杂度

堆排序的空间复杂度

堆排序的优缺点

优点：

缺点：

堆排序与快速排序的比较

总结

冒泡排序

冒泡排序的基本原理

冒泡排序的代码实现（C++ 示例）

代码说明

冒泡排序的时间复杂度

冒泡排序的空间复杂度

冒泡排序的优缺点

优点：

缺点：

冒泡排序与其他排序算法的比较

总结

二分查找

二分查找的基本原理

二分查找的代码实现（C++ 示例）

迭代实现

递归实现

时间和空间复杂度

二分查找的优缺点

优点：

缺点：

常见变种

示例：查找第一个大于等于目标值的元素

总结

热门标签