c++算法与函数
2026-08-19 11:17:33
发布于：浙江
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; };
全部评论 4
顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶 顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶2026-08-31 来自 上海
1
有帮助，赞一个