本文最后更新于23 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com
5天速成数据结构与算法-Day1
排序
冒泡排序
介绍
冒泡排序（Bubble Sort）的核心思想非常简单：从头开始，不断比较相邻的两个元素，如果前者比后者大，就交换位置。 这样从头到尾完整地走一趟，最大的那个元素就必然会“沉”到队尾的最终位置。只需不断重复这个过程，每一轮都将当前未排序部分的最大值找出来送到末端，直到所有元素都排列整齐。因为在这个过程中较小的元素会像气泡一样逐渐“冒”到数组的前方，所以叫冒泡排序故得此名。
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换它们
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
- 这步做完后，最后的元素会是最大的数
- 针对所有的元素重复以上的步骤，除了已经是最大数的最后一个
- 持续每次对越来越少(每次重复都会少一个最大数)的元素重复上面的步骤，直到没有任何一对数字需要比较
基础实现
#include <iostream>
#include <vector>
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
// 如果当前元素大于下一个元素，则交换
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 打印数组
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
std::cout << "排序前：";
printArray(arr);
bubbleSort(arr);
std::cout << "排序后：";
printArray(arr);
return 0;
}
快速排序
介绍
快速排序（Quick Sort）是一种极其高效的分治排序算法，也是实际应用中最常用的排序算法之一。
它的核心思想可以概括为“选个基准，然后左右站队”：
- 选基准(pivot)：首先，从数组中任意选择一个元素作为“基准”。
- 站队：接着，重新排列数组，将所有小于基准的元素移动到基准的左边，所有大于等于基准的元素移动到右边。这一步完成后，该基准元素就找到了它在最终有序序列中的“最终位置”。
- 分而治之：最后，对基准左右两边的子数组（现在它们是两个独立的、更小的问题），递归地重复上述过程，直到每个子数组都排序完毕。
通过这种巧妙的“分而治之”策略，快速排序能将一个大问题不断分解成小问题来解决，平均时间复杂度能达到卓越的 O(nlogn)。
算法步骤
- 从数列中选择一个元素作为”基准”，本文采用最左侧元素作为基准
- 将所有比基准值小的元素放到基准前面，所有比基准值大的元素放到基准后面（分区操作）
- 对基准左右两个子序列分别重复步骤1和2，直到子序列只有一个元素或为空
代码实现
#include <iostream>
#include <vector>
int partition(std::vector<int>& arr, int low, int high) {
// 选择最左侧元素作为基准
int pivot = arr[low];
int i = low + 1;
for (int j = low + 1; j <= high; j++) {
// 将小于基准的元素移到左侧
if (arr[j] < pivot) {
// 交换元素
std::swap(arr[i], arr[j]);
i++;
}
}
// 将基准元素放到正确位置
std::swap(arr[low], arr[i - 1]);
return i - 1;
}
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);
}
}
// 打印数组
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> arr = {10, 7, 8, 9, 1, 5};
std::cout << "排序前：";
printArray(arr);
quickSort(arr, 0, arr.size() - 1);
std::cout << "排序后：";
printArray(arr);
return 0;
}
归并排序
介绍
归并排序（Merge Sort）是一种高效且稳定的“分治”排序算法。其核心策略可以概括为“先递归拆分，再有序合并”。它会持续地将一个大数组对半切分，直到每个部分都只剩一个元素（此时天然有序）。接着，再反向地将这些相邻的有序部分两两配对，按大小顺序合并成一个更长的有序数组，不断重复此过程，直到最终还原成一个完整的有序序列。
归并排序的性能极其稳定，无论原始序列是好是坏，时间复杂度都保持在卓越的 O(nlogn)。与快速排序的“就地交换”不同，它通过“有序合并”实现排序，这一特性也保证了其排序的稳定性（相同元素的原始相对顺序在排序后不会改变），但通常需要额外的存储空间来辅助合并操作。
算法步骤
- 将待排序数组递归地分割成两半，直到每个子数组只包含一个元素（此时认为子数组已排序）
- 递归地合并相邻的子数组，合并时比较两个子数组的元素，按顺序放入临时数组（核心）
- 将临时数组中的元素复制回原数组对应的位置
- 重复步骤2和3，直到所有子数组合并成一个完整的有序数组
算法实现
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
// 计算两个子数组的大小
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
std::vector<int> L(n1);
std::vector<int> R(n2);
// 复制数据到临时数组
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 合并临时数组
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制L的剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 复制R的剩余元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
// 找出中间点
int mid = left + (right - left) / 2;
// 递归排序左右两半
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并已排序的两半
merge(arr, left, mid, right);
}
}
// 打印数组
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
std::cout << "排序前：";
printArray(arr);
mergeSort(arr, 0, arr.size() - 1);
std::cout << "排序后：";
printArray(arr);
return 0;
}
插入排序
介绍
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作方式类似于我们打牌时的整理牌序，它将待排序序列分为两部分：已排序部分和未排序部分。算法不断地从未排序部分取出元素，然后插入到已排序部分的正确位置，直到所有元素都排序完毕。
算法步骤
- 将第一个元素视为已排序序列，其余元素视为未排序序列
- 从未排序序列中取出第一个元素，称为”待插入元素”
- 从已排序序列的末尾开始，依次与待插入元素比较
- 如果已排序序列中的元素大于待插入元素，则将该元素后移一位
- 重复步骤3和4，直到找到小于或等于待插入元素的位置
- 将待插入元素插入到该位置
- 重复步骤2至6，直到未排序序列为空
算法实现
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i]; // 当前待插入元素
int j = i - 1;
// 将大于key的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 插入元素
arr[j + 1] = key;
}
}
// 打印数组
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6};
std::cout << "排序前：";
printArray(arr);
insertionSort(arr);
std::cout << "排序后：";
printArray(arr);
return 0;
}
堆排序
介绍
堆排序（Heap Sort）是一种高效的原地排序算法，它巧妙地利用了“堆”数据结构。其核心思想是首先将待排序的数组重构成一个最大堆（Max Heap）。在最大堆中，根节点（数组的第一个元素）始终是所有元素中的最大值。
构建好最大堆后，算法将堆顶的最大元素与堆末尾的元素交换，从而将当前的最大值放置到数组的正确最终位置。接着，将堆的大小减一，并对剩余的元素进行“堆化”调整，确保新的根节点仍然是剩余元素中的最大值。此过程不断重复——交换、缩小堆、重新堆化——直到所有元素都被放置到其最终的有序位置，完成整个排序。
堆（Heap）是一种特殊的完全二叉树结构，它的两个重要特性：
- 堆是一个完全二叉树，除了最底层外，其他层的节点都是满的，最底层的节点从左到右填充。
- 在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。
堆的数组表示：
虽然堆是一种树结构，但是也可以用数组高效地表示，这是堆的一个重要特性。
对于数组中索引为 i 的节点：
其左子节点的索引为 2*i + 1
其右子节点的索引为 2*i + 2
这种表示方法非常紧凑，不需要使用额外的指针，充分利用了完全二叉树的性质。
算法步骤
- 将无序序列构建成一个最大堆
- 将堆顶元素（最大值）与堆的最后一个元素交换
- 剔除最后一个元素（已排序），将剩余元素重新构建为最大堆
- 重复步骤2和3，直到堆中只剩下一个元素
算法实现
#include <iostream>
#include <vector>
void heapify(std::vector<int>& arr, int n, int root) {
int largest = root; // 初始化最大值为根节点
int left = 2 * root + 1; // 左子节点
int right = 2 * root + 2; // 右子节点
// 如果左子节点大于根节点
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右子节点大于当前最大值
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大值不是根节点
if (largest != root) {
// 交换根节点和最大值
std::swap(arr[root], 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);
}
}
// 打印数组
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
std::cout << "排序前：";
printArray(arr);
heapSort(arr);
std::cout << "排序后：";
printArray(arr);
return 0;
}
查找
二分查找
介绍
二分查找（Binary Search）是一种高效的查找算法，也叫折半查找。核心思想：对于一个有序的数据集合，每次查找都将查找范围缩小为原来的一半，直到找到目标值或确定目标值不存在。二分查找要求数据必须是有序的，经常应用于数组等支持随机访问的数据结构里。跟线性查找相比，二分查找的效率要高得多，特别是对于大规模数据集。
算法步骤
- 确定查找范围的左边界 left 和右边界 right
- 计算中间位置 mid = (left + right) / 2（注意整数溢出问题，更安全的做法是 mid = left + (right – left) / 2）
- 将中间位置的元素与目标值比较
- 如果中间元素等于目标值，查找成功，返回中间元素的位置
- 如果中间元素大于目标值，目标值可能在左半部分，将右边界调整为 mid – 1
- 如果中间元素小于目标值，目标值可能在右半部分，将左边界调整为 mid + 1
- 重复步骤2-3，直到找到目标值或者左边界大于右边界（此时表示目标值不存在）
算法实现
#include <iostream>
#include <vector>
// 迭代实现
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
// 递归实现
int binarySearchRecursive(const std::vector<int>& arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return binarySearchRecursive(arr, target, left, mid - 1);
} else {
return binarySearchRecursive(arr, target, mid + 1, right);
}
}
int main() {
std::vector<int> arr = {2, 3, 4, 10, 40, 50, 70, 80};
int target = 10;
// 迭代方法
int result = binarySearch(arr, target);
if (result == -1) {
std::cout << "元素 " << target << " 不存在于数组中" << std::endl;
} else {
std::cout << "元素 " << target << " 在数组中的索引为 " << result << std::endl;
}
// 递归方法
result = binarySearchRecursive(arr, target, 0, arr.size() - 1);
if (result == -1) {
std::cout << "元素 " << target << " 不存在于数组中" << std::endl;
} else {
std::cout << "元素 " << target << " 在数组中的索引为 " << result << std::endl;
}
return 0;
}
字符串匹配
Rabin-Karp算法
介绍
Rabin-Karp算法是一种基于哈希函数的字符串匹配算法，由 Michael O. Rabin 和 Richard M. Karp 于1987年提出，核心思想是用哈希函数将模式串和文本串中的子串转换为数值进行比较，避免大量不必要的字符比较。这个算法特别适合多模式串匹配场景，时间复杂度平均为O(n+m)，n是文本串长度，m是模式串长度。
Rabin-Karp算法的关键在于使用滚动哈希函数（Rolling Hash），它可以在常数时间内计算出滑动窗口的新哈希值，保证算法在大多数情况下的高效性。
算法步骤
- 计算模式串的哈希值
- 计算文本串中长度为m的第一个子串的哈希值（m为模式串长度）
- 在文本串上滑动窗口，对于每个位置：
- 使用滚动哈希技术高效计算当前窗口的哈希值
- 如果哈希值与模式串相等，则进行字符逐一比较以避免哈希冲突
- 如果完全匹配，则找到一个匹配位置
- 重复步骤3，直到处理完整个文本串
####
