C++ 算法的知识
2026-08-28 14:51:35
发布于：浙江
整理了一下 C++ 算法的知识
C++ 四大基础排序算法详解
鸡尾酒 · 冒泡 · 插入 · 选择排序详解
目录
- 鸡尾酒排序原理与代码
- 鸡尾酒排序示例与性能
- 冒泡排序程序推演
- 冒泡排序代码与复杂度
- 直接插入排序原理与代码
- 直接插入排序性能特点
- 直接选择排序原理与代码
- 直接选择排序应用场景
- 总结与对比
一、鸡尾酒排序
1.1 原理与代码
算法原理
• 双向冒泡：交替从左到右、从右到左遍历，将最大/最小值归位
• 边界收缩：每轮完成后，已排序的边界向内收缩，减少比较范围
• 提前终止：若一整轮双向遍历均无元素交换，说明已排序，可提前结束
运行示例
• 初始: [ 5, 3, 8, 4, 2 ]
• L→R: [ 3, 5, 4, 2, 8 ]
• R→L: [ 2, 3, 4, 5, 8 ]
• L→R: [ 2, 3, 4, 5, 8 ] → 完成
性能特点
• 时间复杂度: 最坏/平均 O(n²)，最优 O(n)
• 空间复杂度: O(1)，原地排序
• 稳定性: 稳定
1.2 示例与性能
排序过程示例
• 初始数组: [ 5, 3, 8, 4, 2 ]
• 第一轮 (L→R): [ 3, 5, 4, 2, 8 ]
• 第二轮 (R→L): [ 3, 2, 4, 5, 8 ]
• 第三轮 (L→R): [ 2, 3, 4, 5, 8 ]
性能特性分析
• 时间复杂度: 最坏/平均 O(n²)，最优 O(n)
• 空间复杂度: O(1)，原地排序
• 稳定性: 稳定 (相等元素相对位置不变)
• 优化效果: 相比冒泡排序，双向遍历能更快将小数冒到前面，减少总轮次
二、冒泡排序
2.1 程序推演
• 初始: [5, 3, 8, 1, 2]
第1轮：最大值8归位
• 5>3 → [3, 5, 8, 1, 2]
• 8>1 → [3, 5, 1, 8, 2]
• 8>2 → [3, 5, 1, 2, 8]
• 结果: 已排序 [ 8 ]
第2轮：次大值5归位
• 当前: [3, 5, 1, 2, 8]
• 5>1 → [3, 1, 5, 2, 8]
• 5>2 → [3, 1, 2, 5, 8]
• 结果: 已排序 [ 5, 8 ]
第3轮：第三大值3归位
• 当前: [3, 1, 2, 5, 8]
• 3>1 → [1, 3, 2, 5, 8]
• 3>2 → [1, 2, 3, 5, 8]
• 结果: 已排序 [ 3, 5, 8 ]
第4轮：检查有序并终止
• 当前: [1, 2, 3, 5, 8]
• 1<2 → 不交换，本轮无交换, 提前终止
• 完成: [ 1, 2, 3, 5, 8 ]
2.2 代码与复杂度
C++实现代码（带优化）· 实现要点
• 使用 swapped 标志位检测交换，若无交换则提前终止
• 内层循环范围逐轮缩小 ( n-1-i )，减少冗余比较
• 利用 std::swap() 函数简化元素交换操作
复杂度与稳定性
• 时间复杂度: 最好情况 O(n)；最坏情况 O(n²)；平均情况 O(n²)
• 空间复杂度: O(1)，属于原地排序算法
• 稳定性: 稳定排序，相等元素的相对顺序保持不变
三、直接插入排序
3.1 原理与代码
算法原理
• 类比扑克牌，新牌插入已排序的手牌
• 从未排序区取元素，在已排序区反向扫描
• 找到位置，将更大元素后移，插入新元素
C++实现代码（基础版本）
// 基础版本实现
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are
// greater than key, to one position ahead
// of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
性能特点
• 时间复杂度: 最好 O(n)，最坏/平均 O(n²)
• 空间复杂度: O(1)，原地排序
• 稳定性: 稳定
• 优点: 实现简单，小数据高效
适用场景
• 小规模数据排序 (n ≤ 1000)
• 数据近乎有序，效率接近 O(n)
• 资源受限的嵌入式或内存紧张环境
3.2 性能特点
时间与空间复杂度
• 最好情况： O(n)，输入已有序，仅需n-1次比较
• 最坏/平均： O(n²)，输入逆序或随机，比较和移动次数多
• 空间复杂度： O(1)，原地排序，仅用常数额外空间
稳定性与效率特征
• 稳定排序： 相等元素相对顺序不变
• 小规模高效： 数据量小时，实际性能优于O(n log n)算法
• 近有序高效： 接近O(n)，适用于增量更新
优缺点总结
• 优点： 实现简单、对小数据高效、稳定、原地排序
• 缺点： 大规模数据效率低，因元素需频繁后移
• 工程价值： 常作为更复杂排序（快排/归并）的子过程
适用场景
• 小规模数据排序 (n < 1000)
• 数据基本有序的场景
• 需要稳定排序的场景
• 资源受限环境（如嵌入式系统）
四、直接选择排序
4.1 原理与代码
算法原理
• 基于贪心策略：每轮从未排序区中选出最小元素
• 将最小元素与未排序区首元素交换，逐步构建有序序列
• 具有“找—换—缩”三步循环机制，逻辑清晰直观
C++实现代码 · 要点说明
• 基础版本使用双重循环：外层控制轮次，内层查找最小值索引
• 通过 swap() 函数完成元素交换，避免额外移动操作
• 模板版本支持任意类型与自定义比较函数，提升通用性
核心特性
• 时间复杂度：所有情况均为O(n²)，比较次数固定
• 空间复杂度：O(1)，仅需常数级额外空间，属原地排序
• 稳定性：不稳定，相等元素相对顺序可能被破坏
适用场景
• 小规模数据排序（n ≤ 100），实现简单
• 内存受限环境（如嵌入式系统），空间开销极低
• 教学演示用途，帮助初学者理解排序基本概念
4.2 应用场景
小规模数据处理
• 适用于 n ≤ 100 的小规模数组排序
• 实现简单，常数因子小，实际性能可能更优
• 在数据量较小时，性能优势明显
教学与学习用途
• 算法逻辑直观，是数据结构课程的入门案例
• 代码简洁（约15行），适合作为编码练习任务
• 有助于理解循环不变式、渐进分析等核心概念
资源受限环境
• 空间复杂度 O(1)，无需额外辅助空间
• 适合嵌入式、微控制器等内存紧张的设备
• 交换次数少，适用于写操作昂贵的环境
特殊数据结构适配
• 可适配单链表，仅需修改指针即可交换
• 效率优于依赖随机访问的其他算法
• 适用于磁盘排序等交换成本高的场景
五、总结与对比
算法 时间复杂度 (最好/平均/最坏) 空间复杂度 稳定性 适用场景
鸡尾酒排序 O(n) / O(n²) / O(n²) O(1) 稳定 数据接近有序时效率较高
冒泡排序 O(n) / O(n²) / O(n²) O(1) 稳定 小规模或接近有序数据集
直接插入排序 O(n) / O(n²) / O(n²) O(1) 稳定 小规模数据(n≤1000)、基本有序数据流
直接选择排序 O(n²) / O(n²) / O(n²) O(1) 不稳定 内存受限、交换次数敏感场景
望大家多点赞，多讨论，若有错误，欢迎告诉我
打个广告
加团队
这里空空如也
有帮助，赞一个