c算法与函数
一、 算法基础概念
算法是解决特定问题的一系列有限、确定且可行的指令序列。在 C 中，算法通常体现为对数据的处理逻辑。
算法的五大特征：
有穷性：算法必须在执行有限步骤后停止，不能陷入死循环。
确定性：每一步骤必须有精确的定义，无歧义。
可行性：每一步都必须在有限时间内完成。
输入：算法可以有零个或多个输入量值。
输出：算法必须至少有一个输出结果。
算法与程序的区别：
算法是解决问题的逻辑方法，而程序是算法在特定编程语言（如 C++）中的具体实现。
二、 常用排序算法
排序是将一组数据按照特定顺序（如升序或降序）排列的过程。以下是几种经典的 C++ 排序实现思路：
冒泡排序 (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]) {
stdswap(arr[j], arr[j + 1]);
}
}
}
}
//
选择排序 (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;
}
}
stdswap(arr[i], arr[minIndex]);
}
}
//
快速排序 (Quick Sort)
原理：基于分治算法思想。选择一个基准值（Pivot），将数组分为两部分：左侧小于等于基准值，右侧大于基准值，然后递归地对这两部分进行排序。
特点：平均效率高，时间复杂度为
O(n log n)
O(n log n)，是实际应用中常用的排序算法。
核心逻辑：
选取基准值（通常选中间位置 (left + right) / 2）。
使用两个指针 i 和 j，分别从左向右找比基准大的数，从右向左找比基准小的数，找到后交换。
当 i > j 时停止，递归处理左右子区间。
其他常见排序
C++ 标准库及算法大全中还包含插入排序、归并排序、堆排序、希尔排序、计数排序、桶排序和基数排序等，可根据数据规模和特性选择使用。
三、 搜索算法
搜索算法用于在数据集中查找特定目标值。
线性搜索 (Linear Search)：逐个检查元素，适用于未排序数据，时间复杂度
O(n)
O(n)。
二分搜索 (Binary Search)：适用于已排序数组。通过不断将搜索区间减半来查找目标，时间复杂度
O(log n)
O(log n)。
其他搜索：插值搜索、斐波那契搜索等，针对特定分布的数据优化搜索效率。
四、 高精度算法 (High Precision Arithmetic)
由于 C++ 内置类型（如 int, long long, double）的范围和精度有限，处理超大整数或高精度浮点数时需要模拟人工运算。
高精度加法
思路：使用字符串或字符数组输入大数，将其逆序存储到整型数组中（个位在下标 0）。从低位到高位依次相加，处理进位。
关键点：
对齐个位：通常通过逆序存储自然对齐。
进位处理：sum = a[i] + b[i] + carry，当前位结果为 sum % 10，进位为 sum / 10。
注意最高位可能产生的额外进位。
高精度乘法与除法
乘法：模拟竖式乘法，注意位权对应关系。
除法：
高精度除以单精度：从高位到低位逐位计算商和余数。
单精度除以单精度求高精度商：先算整数部分，余数乘以 10 继续除，可保留任意位小数。
压位优化
思想：为了减少计算次数，可以将多位数字压缩到一个数组元素中（例如每 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）能极大提升代码编写效率和程序性能。
函数的基本结构
一个完整的函数定义通常包含以下四个部分：
返回值类型：函数执行后返回的数据类型。如果不返回任何值，使用 void。
函数名：遵循标识符命名规则，应清晰描述函数功能。
参数列表：括号内定义的输入变量（形参），包括类型和名称。可以为空。
函数体：花括号 {} 内的代码块，包含具体的逻辑语句。
语法示例：
cpp
返回值类型 函数名(参数列表) {
// 函数体
return 表达式; // 如果返回值类型不是 void
}
// 示例：计算两个整数之和
int add(int a, int b) {
return a + b;
}
2. 函数的声明与定义
函数声明（原型）：告诉编译器函数的存在、返回类型和参数类型。通常放在头文件（.h）中。
格式：int add(int a, int b);
作用：允许在定义之前调用函数，支持多文件编程。
函数定义：提供函数的实际实现代码。通常放在源文件（.cpp）中。
规则：声明可以多次，但定义在整个程序中只能有一次（遵循单一定义规则 ODR）。
3. 参数传递方式
C++ 主要有三种参数传递方式，区别在于是否影响原始数据以及性能开销：
表格
传递方式 说明 特点 示例语法
值传递 复制实参的值给形参 安全，修改形参不影响实参；大对象拷贝开销大默认方式 void func(int x)
引用传递 形参是实参的别名 高效（无拷贝），可直接修改实参；C++ 推荐方式 void func(int& x)
指针传递 传递实参的地址 可修改实参，语法稍繁琐（需解引用 ） void func(int x)
注意：若希望提高效率且防止修改实参，常使用 常量引用 (const Type&)。
常见高级特性
函数重载 (Function Overloading)
允许在同一作用域中声明多个同名函数，只要它们的参数列表不同（参数个数、类型或顺序不同）。
注意：仅返回值类型不同不能构成重载。
cpp
int add(int a, int b);
double add(double a, double b); // 合法重载
默认参数 (Default Arguments)
可以在函数声明中为参数指定默认值。调用时若省略该参数，则使用默认值。
规则：默认参数必须从右向左依次定义，不能跳过中间参数。
cpp
void printInfo(string name, int age = 18);
printInfo("Alice"); // age 默认为 18
内联函数 (Inline Functions)
使用 inline 关键字建议编译器在调用处直接替换函数体，以减少函数调用的开销。
适用场景：代码短小（如1-5行）、频繁调用的函数。
缺点：代码过长会导致代码膨胀。
5. 特殊函数类型
main 函数：每个 C++ 程序的入口点。
递归函数函数内部调用自身。需注意设置终止条件，避免栈溢出。
Lambda 表达式：匿名函数，常用于算法标准库（如 std::sort）中作为简短回调。
cpp
auto sum = [](int a, int b) { return a + b; };
