跳到主要内容C++ 七大排序算法详解 | 极客日志C++算法
C++ 七大排序算法详解
综述由AI生成详细解析了 C++ 中的七大排序算法,包括选择、冒泡、计数、插入、堆、快速及归并排序。涵盖各算法的思路、时间复杂度、空间复杂度及稳定性分析,并提供完整代码实现。通过对比表格总结了不同算法的适用场景,帮助开发者根据数据规模与特性选择合适的排序方案。
RedisGeek17 浏览 一、选择排序
1. 思路
- 双层循环,遍历数组找到每次的最大值,记录最大值下标
index,将最大值与最后一个值交换:swap(nums[index], nums[n-1])。
- 在剩下元素中,重复上述操作,直至数组排序完成:
swap(nums[index], nums[n-2]),一般形式为 swap(nums[index], nums[nums.size() - i])。
2. 平均时间复杂度:O(n^2)
- 过程:
- 总结:
- 元素交换次数为 k(k < n-1 次)。
- 时间复杂度 = 比较次数 + 交换次数。
- 所以复杂度为:O(1+2+3+...+n-1+k) = O(n*(n-1)/2+k) = O(n²)
| 迭代次数 | 元素个数 | 还需比较次数 |
|---|
| 第一次 | n | n-1 |
| 第二次 | n-1 | n-2 |
| 第 n-1 次 | 2 | 1 |
| 第 n 次 | 1 | 0 |
3. 空间复杂度:O(1)
4. 稳定性:不稳定
- 例子:数组
3 2 3 1 从小到大排序(小的放前面),排序后第一个 3 在第二个 3 之前。
代码示例:
#include<iostream>
#include<vector>
using namespace std;
void selectSort(vector<int> &nums) {
for (int i = 1; i < nums.size(); i++) {
int index = 0;
for (int j = ; j <= nums.() - i; j++) {
(nums[index] < nums[j]) index = j;
}
(nums[index], nums[nums.() - i]);
}
}
{
vector<> vec = { ,,,,,, };
(vec);
( it : vec) {
cout << it << ;
}
;
}
1
size
if
swap
size
int main()
int
2
1
7
4
-1
3
5
selectSort
for
auto
" "
return
0
二、冒泡排序
1. 思路
- 冒泡排序就是通过不断比较相邻元素:如果它们顺序有错误,就交换它们的位置,让较大的元素(或较小的元素)逐渐'冒泡'移动到列表的一端,经过多次循环这样的过程,最终使得整个列表变得有序。
2. 时间复杂度:O(n) ~ O(n^2)
- 最好情况(已排序)为 O(n),最坏情况(逆序)为 O(n^2)。
3. 空间复杂度:O(1)
4. 稳定性:稳定
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void Bubble_Sort(vector<int>& vec) {
for (int i = 0; i < vec.size() - 1; i++) {
bool flag = 1;
for (int j = 0; j < vec.size() - 1 - i; j++) {
swap(vec[j], vec[j + 1]);
flag = 0;
}
if (flag) return;
}
}
int main() {
vector<int> vec = { 4,3,1,5,9,2 };
Bubble_Sort(vec);
for (auto it : vec) {
cout << it << " ";
}
return 0;
}
三、计数排序(桶排下标)
1. 思路
- 将数值作为桶号,遍历整个数组,对相应的桶进行计数。
- 遍历原数组,找到最大值
max,申请 max+1 个空间的 bucket 数组(桶),初始化为 0,下标:0-max(vector bucket(max+1,0))。
- 遍历原数组,找到每个数值对应的桶号,并对桶计数
++,即 bucket[vec[i]]++。
- 遍历桶数组,根据桶内计数取出下标值,放入原数组中。
2. 时间复杂度:O(n)
3. 空间复杂度:O(m)
4. 稳定性:不稳定
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void Bucket_Sort(vector<int>& vec) {
int vec_max = vec[0];
for (auto it : vec) {
vec_max = vec_max > it ? vec_max : it;
}
vector<int> bucket(vec_max + 1, 0);
for (auto it : vec) {
bucket[it]++;
}
int idx = 0;
for (int i = 0; i < bucket.size(); i++) {
while (bucket[i] > 0) {
vec[idx++] = i;
bucket[i]--;
}
}
}
int main() {
vector<int> vec = { 4,3,1,5,9,2,1,2,1,7,1 };
Bucket_Sort(vec);
for(auto it:vec) cout<<it<<" ";
return 0;
}
四、插入排序(两个下标)
1. 思路
- 将数组分为有序与无序两部分,每次从无序表取出一个元素,插入到有序表的适当位置。开始时有序表只有一个元素,无序表有 n-1 个数。
- 每遍历一次,有序表元素增加 1,无序表减少 1,重复 n-1 次。
2. 时间复杂度:O(n) ~ O(n^2)
- 最好情况(已排序)为 O(n),最坏情况(逆序)为 O(n^2)。
3. 空间复杂度:O(1)
4. 稳定性:稳定
#include<iostream>
#include<vector>
using namespace std;
void insert_Sort(vector<int>& vec) {
for (int i = 1; i < vec.size(); i++) {
int temp = vec[i];
int j = i - 1;
for (; j >= 0; j--) {
if (temp < vec[j]) {
vec[j + 1] = vec[j];
} else {
break;
}
}
vec[j + 1] = temp;
}
}
int main() {
vector<int> vec = { 7,1,3,4,0,6 };
insert_Sort(vec);
for (auto it : vec) {
cout << it << " ";
}
return 0;
}
五、堆排序
1. 思路
- 首先,从最后一个非叶子节点开始,自底向上调整数组使其成为最大堆,确保每个父节点都大于其子节点。
- 然后,重复将堆顶元素(最大值)与当前末尾元素交换,并调整剩余部分使其重新成为最大堆,最终实现排序。这一过程的时间复杂度为 O(n log n),空间复杂度为 O(1)(原地排序),但稳定性较差,因为相同元素的相对顺序可能改变。
2. 时间复杂度:O(n \log n)
3. 空间复杂度:O(1)
4. 稳定性:不稳定
#include<iostream>
#include<vector>
using namespace std;
void adjustHeap(vector<int>& vec, int start, int end) {
int father = start;
int child = 2 * father + 1;
while (child <= end) {
if (child + 1 <= end && vec[child + 1] > vec[child]) {
child++;
}
if (vec[child] > vec[father]) {
swap(vec[child], vec[father]);
father = child;
child = 2 * father + 1;
} else {
return;
}
}
}
void HeapSort(vector<int>& vec) {
for (int i = vec.size() / 2 - 1; i >= 0; i--)
{
adjustHeap(vec, i, vec.size() - 1);
}
for (int i = vec.size() - 1; i >= 1; i--) {
swap(vec[0], vec[i]);
adjustHeap(vec, 0, i - 1);
}
}
int main() {
vector<int> vec = { 53,17,22,89,33,45,12 };
HeapSort(vec);
for (auto it : vec) {
cout << it << " ";
}
return 0;
}
六、快速排序
快速排序是一种分治算法,通过选择基准元素将序列分区,然后递归排序子序列。以下是两种版本:一个是三色旗分区(用于特定问题),另一个是完整的递归实现。
1. 三色旗分区版本
- 问题背景:此版本针对类似'荷兰国旗问题'的场景,序列只包含三种值(例如 0、1、2)。算法将序列分为三个区域:小于基准、等于基准、大于基准。
- 时间复杂度:O(n),因为它只遍历序列一次进行分区。
- 算法步骤:
- 初始化指针:
i(左边界)、j(右边界)、index(当前索引)。
- 遍历序列:比较当前元素与基准
temp(通常设为中间值,如 1)。
- 如果
vec[index] == temp,则 index++。
- 如果
vec[index] < temp,则交换到左侧区域(i++ 后交换)。
- 如果
vec[index] > temp,则交换到右侧区域(j-- 后交换)。
- 分区完成后,序列被划分为三个部分。
#include<iostream>
#include<vector>
using namespace std;
void quickSort(vector<int>& vec, int L, int R) {
if (L > R) return;
int temp = 1;
int i = L - 1;
int j = R + 1;
int index = L;
while (index < j) {
if (temp == vec[index]) index++;
else if (temp > vec[index]) swap(vec[++i], vec[index++]);
else swap(vec[--j], vec[index]);
}
}
int main() {
vector<int> vec = { 1,0,2,0,1,1,2,0 };
quickSort(vec, 0, vec.size() - 1);
for (auto it : vec) cout << it << " ";
return 0;
}
2. 完整递归版本(三色旗 + 两次递归)
- 算法描述:在分区的基础上,递归排序左右子序列。基准值选择序列首元素
vec[L]。
- 时间复杂度分析:
- 最好情况:每次分区基准值接近中位数,序列均匀划分。此时时间复杂度:O(n log n),空间复杂度:O(log n)(递归栈深度)。
- 最坏情况:每次基准值是最小或最大值,序列极度不平衡。此时时间复杂度:O(n^2),空间复杂度:O(n)(递归栈深度)。
- 稳定性:不稳定,因为分区过程涉及交换,可能改变相同元素的相对顺序。
#include<iostream>
#include<vector>
using namespace std;
void quickSort(vector<int>& vec, int L, int R) {
if (L > R) return;
int temp = vec[L];
int i = L - 1;
int j = R + 1;
int index = L;
while (index < j) {
if (temp == vec[index]) index++;
else if (temp > vec[index]) swap(vec[++i], vec[index++]);
else swap(vec[--j], vec[index]);
}
quickSort(vec, L, i);
quickSort(vec, j, R);
}
int main() {
vector<int> vec = { 7,3,0,9,4,2,2,6,5 };
quickSort(vec, 0, vec.size() - 1);
for (auto it : vec) cout << it << " ";
return 0;
}
七、归并排序
归并排序是一种分治算法,基于二分法将序列递归分割,然后合并有序子序列。
1. 二分法基础
- 问题背景:二分查找是归并排序的灵感来源,用于在有序序列中高效定位元素。
- 时间复杂度:O(log n),因为每次比较将搜索范围减半。
- 算法步骤:
- 初始化指针:
L(左边界)、R(右边界)。
- 循环:计算中点
mid,比较目标值与 vec[mid]。
- 如果
target < vec[mid],则 R = mid - 1。
- 如果
target > vec[mid],则 L = mid + 1。
- 如果相等,则返回元素。
#include<iostream>
#include<vector>
using namespace std;
int HalfSearch(vector<int>& vec, int target) {
int L = 0;
int R = vec.size() - 1;
while (L <= R) {
int mid = (R - L) / 2 + L;
if (target < vec[mid]) {
R = mid - 1;
} else if (target > vec[mid]) {
L = mid + 1;
} else {
return vec[mid];
}
}
return -1;
}
int main() {
vector<int> vec = { 1,4,2,5,8,3,7,7,2,9 };
int n = HalfSearch(vec, 8);
cout << n;
return 0;
}
2. 归并排序算法
- 算法原理:递归将序列分为两半,排序子序列后合并。核心:合并过程,确保有序性。
- 时间复杂度:O(n log n),因为分割和合并各需 O(log n) 层,每层 O(n) 工作。
- 空间复杂度:O(n),由于需要辅助数组存储合并结果。
- 稳定性:稳定,因为合并时相同元素保持相对顺序(代码中使用
<= 比较)。
#include<iostream>
#include<vector>
using namespace std;
void Merge(vector<int>& vec, int L, int mid, int R) {
vector<int> temp(R - L + 1);
int i = L, j = mid + 1, index = 0;
while (i <= mid && j <= R) {
if (vec[i] <= vec[j]) temp[index++] = vec[i++];
else temp[index++] = vec[j++];
}
while (i <= mid) temp[index++] = vec[i++];
while (j <= R) temp[index++] = vec[j++];
for (int k = 0; k < temp.size(); k++) vec[L + k] = temp[k];
}
void MergeSort(vector<int>& vec, int L, int R) {
if (L >= R) return;
int mid = (R + L) / 2;
MergeSort(vec, L, mid);
MergeSort(vec, mid + 1, R);
Merge(vec, L, mid, R);
}
int main() {
vector<int> vec = { 1,4,2,5,8,3,7,7,2,9 };
MergeSort(vec, 0, vec.size() - 1);
for (auto it : vec) {
cout << it << " ";
}
return 0;
}
八、整体比较与总结
时间复杂度对比
- O(n²) 级别:选择排序、冒泡排序、插入排序。适用于小规模数据或部分有序数据,其中插入排序在接近有序时效率最高(接近 O(n))。
- O(n log n) 级别:堆排序、快速排序、归并排序。适合大规模数据,快速排序平均性能最优,但最坏情况退化为 O(n²);堆排序稳定在 O(n log n);归并排序稳定但需额外空间。
- O(n) 级别:计数排序(桶排)。仅适用于整数且范围较小的数据,空间消耗与数据范围相关。
空间复杂度对比
- 原地排序(O(1)):选择排序、冒泡排序、插入排序、堆排序、快速排序(递归栈空间不计入,但最坏情况下递归深度为 O(n))。
- 非原地排序:归并排序(O(n))、计数排序(O(m),m 为数据范围)。
稳定性对比
- 稳定算法:冒泡排序、插入排序、归并排序。保持相同元素的相对顺序。
- 不稳定算法:选择排序、堆排序、快速排序、计数排序(依赖具体实现)。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学或简单场景 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 接近有序的小数据 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 大规模随机数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 需要稳定性的外部排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 实时数据或 Top K 问题 |
| 计数排序 | O(n) | O(n) | O(m) | 不稳定 | 范围小的整数数据 |
通过对比可见,不同排序算法在时间、空间、稳定性上各有优劣,实际选择需结合数据规模、分布特征及稳定性需求。
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown转HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online