一、 算法基础概念
算法是解决特定问题的一系列有限、确定且可行的指令序列。在 C++ 中，算法通常体现为对数据的处理逻辑。
算法的五大特征：
有穷性：算法必须在执行有限步骤后停止，不能陷入死循环。
确定性：每一步骤必须有精确的定义，无歧义。
可行性：每一步都必须在有限时间内完成。
输入：算法可以有零个或多个输入量值。
输出：算法必须至少有一个输出结果。
算法与程序的区别：
算法是解决问题的逻辑方法，而程序是算法在特定编程语言（如 C++）中的具体实现。
二、 常用排序算法
排序是将一组数据按照特定顺序（如升序或降序）排列的过程。以下是几种经典的 C++ 排序实现思路：
1. 冒泡排序 (Bubble Sort)
原理：通过重复交换相邻的元素来排序。如果前一个数大于后一个数，则交换它们。
特点：简单直观，但效率较低，时间复杂度为
O(n2)
O(n2)。
核心逻辑：
cpp
//
void bubbleSort(int arr[], int length) {
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
//
2. 选择排序 (Selection Sort)
原理每次从未排序的序列中选择最小（或最大）的元素，放到已排序序列的末尾。
特点：交换次数少，但比较次数多，时间复杂度为
O(n2)
O(n2)。
核心逻辑：
cpp
//
void selectionSort(int arr[], int length) {
for (int i = 0; i < length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
//
3. 快速排序 (Quick Sort)
原理：基于分治算法思想。选择一个基准值（Pivot），将数组分为两部分：左侧小于等于基准值，右侧大于基准值，然后递归地对这两部分进行排序。
特点：平均效率高，时间复杂度为
O(n log n)
O(n log n)，是实际应用中常用的排序算法。
核心逻辑：
选取基准值（通常选中间位置 (left + right) / 2）。
使用两个指针 i 和 j，分别从左向右找比基准大的数，从右向左找比基准小的数，找到后交换。
当 i > j 时停止，递归处理左右子区间。
4. 其他常见排序
C++ 标准库及算法大全中还包含插入排序、归并排序、堆排序、希尔排序、计数排序、桶排序和基数排序等，可根据数据规模和特性选择使用。
三、 搜索算法
搜索算法用于在数据集中查找特定目标值。
线性搜索 (Linear Search)：逐个检查元素，适用于未排序数据，时间复杂度
O(n)
O(n)。
二分搜索 (Binary Search)：适用于已排序数组。通过不断将搜索区间减半来查找目标，时间复杂度
O(log n)
O(log n)。
其他搜索：插值搜索、斐波那契搜索等，针对特定分布的数据优化搜索效率。
四、 高精度算法 (High Precision Arithmetic)
由于 C++ 内置类型（如 int, long long, double）的范围和精度有限，处理超大整数或高精度浮点数时需要模拟人工运算。
1. 高精度加法
思路：使用字符串或字符数组输入大数，将其逆序存储到整型数组中（个位在下标 0）。从低位到高位依次相加，处理进位。
关键点：
对齐个位：通常通过逆序存储自然对齐。
进位处理：sum = a[i] + b[i] + carry，当前位结果为 sum % 10，进位为 sum / 10。
注意最高位可能产生的额外进位。
2. 高精度乘法与除法
乘法：模拟竖式乘法，注意位权对应关系。
除法：
高精度除以单精度：从高位到低位逐位计算商和余数。
单精度除以单精度求高精度商：先算整数部分，余数乘以 10 继续除，可保留任意位小数。
3. 压位优化
思想：为了减少计算次数，可以将多位数字压缩到一个数组元素中（例如每 4 位存为一个 int，基数 base=10000）。
优势：大幅减少数组长度和循环次数，提高运算效率。
输出注意：最高位正常输出，后续低位需补零至固定宽度（如 %04d）。
五、 C++ 标准库与工程实践
在实际开发或竞赛中，合理利用 C++ 标准库可以简化算法实现。
头文件：推荐使用 <bits/stdc++.h> 包含所有标准库，或根据需要包含 <iostream>, <vector>, <algorithm> 等。
命名空间：使用 using namespace std; 避免每次调用标准库函数前加 std::。
容器与算法：
stdvector：动态数组，支持随机访问。
stdsort：标准库提供的排序函数，底层通常为内省排序（IntroSort），效率高于手写的简单排序。
std::swap：高效交换两个变量的值。
数据类型选择：
普通整数用 int。
较大整数用 long long。
高精度计算需自定义结构体或使用字符串模拟。
六、 总结
掌握 C++ 算法需要从理解基本数据结构开始，熟练运用排序和搜索等基础算法，并在面对超出原生数据类型范围的问题时，能够灵活运用高精度算法进行模拟。同时，熟悉 C++ 标准库（STL）能极大提升代码编写效率和程序性能。
