C++：七大排序算法全面解析
目录
一、选择排序
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++) { //遍历n-1轮 int index = 0; for (int j = 1; j <= nums.size() - i; j++) { //找最大值下标,找n-1轮 if (nums[index] < nums[j]) index = j; } //交换最大值和最后一个位置的值 swap(nums[index], nums[nums.size() - i]); } } int main() { vector<int> vec = { 2,1,7,4,-1,3,5 }; selectSort(vec); for (auto it : vec) { cout << it << " "; } 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（vectorbucket(max+1,0)）。 - 遍历原数组，找到每个数值对应的桶号，并对桶计数
++，即bucket[vec[i]]++。 - 遍历桶数组，根据桶内计数取出下标值，放入原数组中。
- 遍历原数组，找到最大值
2. 时间复杂度：O(n)
- 线性时间，依赖于输入范围。
3. 空间复杂度：O(m)
- m 为最大值
max，需要额外空间。
4. 稳定性：不稳定
- 相同元素可能改变顺序。
代码示例：
#include<iostream> #include<vector> #include<algorithm> using namespace std; void Bucket_Sort(vector<int>& vec) { //找出vec最大值 int vec_max = vec[0]; for (auto it : vec) { vec_max = vec_max > it ? vec_max : it; } //创建bucket数组：大小为：max+1 vector<int>bucket(vec_max + 1, 0); //代表bucket数组中有vec_max+1个0 // 使用bucket记录vec中的元素个数 for (auto it : vec) { bucket[it]++; //统计个数 } //遍历bucket输出 for (int i = 0; i < bucket.size(); i++) { while (bucket[i] > 0) { cout << i << " "; bucket[i]--; } } } int main() { vector<int> vec = { 4,3,1,5,9,2,1,2,1,7,1 }; Bucket_Sort(vec); 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]; //要插入的元素 //j-有序部分最后一个元素位置 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 strat, int end) { int father = strat; //根节点 int child = 2 * father + 1; //左子树 //while 循环为了调整最大堆的过程中破坏子树结构，继续向下调整 while (child <= end) { //因为child是左子树，根节点要大于左右子树，所以在子树中找最大的与根节点比较 //防止右子树越界在数组中下标为child+1元素，child就是子树中最大的元素 if (child + 1 <= end && vec[child + 1] > vec[child]) { 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--) //vec.size()/2-1是完全二叉树中最后一个有子节点子树的根 { adjustHeap(vec, i, vec.size() - 1); } for (int i = vec.size() - 1; i >= 1; i--) { swap(vec[0], vec[i]); //只有下标为0的元素被打乱，从根节点开始向下调整 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 << " "; //12 17 22 33 45 53 89 } return 0; } 六、快速排序
快速排序是一种分治算法，通过选择基准元素将序列分区，然后递归排序子序列。以下是两种版本：一个是三色旗分区（用于特定问题），另一个是完整的递归实现
- 问题背景：此版本针对类似“荷兰国旗问题”的场景，序列只包含三种值（例如0、1、2）。算法将序列分为三个区域：小于基准、等于基准、大于基准。
- 时间复杂度：O(n)，因为它只遍历序列一次进行分区。
- 算法步骤：
- 初始化指针：
i（左边界）、j（右边界）、index（当前索引）。 - 遍历序列：比较当前元素与基准
temp（通常设为中间值，如1）。- 如果
vec[index] == temp，则index++。 - 如果
vec[index] < temp，则交换到左侧区域（i++后交换）。 - 如果
vec[index] > temp，则交换到右侧区域（j--后交换）。
- 如果
- 分区完成后，序列被划分为三个部分。
- 初始化指针：
- 算法描述：在分区的基础上，递归排序左右子序列。基准值选择序列首元素
vec[L]。 - 时间复杂度分析：
- 最好情况：每次分区基准值接近中位数，序列均匀划分。此时：
- 时间复杂度：O(n \log n)
- 空间复杂度：O(\log n)（递归栈深度）
- 最坏情况：每次基准值是最小或最大值，序列极度不平衡。此时：
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)（递归栈深度）
- 最好情况：每次分区基准值接近中位数，序列均匀划分。此时：
- 稳定性：不稳定，因为分区过程涉及交换，可能改变相同元素的相对顺序。
- 算法步骤：
- 分区：使用三色旗方法将序列分为三部分（小于、等于、大于基准）。
- 递归：对左右子序列（
L到i和j到R）递归调用快速排序。
代码示例：
void quik(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]); } quik(vec, L, i); quik(vec, j, R); } 以下是完整代码：
#include<iostream> #include<vector> using namespace std; void quik(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++; //和左侧交换 直接index++,因为左侧比较完，交换过来的值一定是temp else if (temp > vec[index]) swap(vec[++i], vec[index++]);//i右移之后和index交换，再index++ else//temp < vec[index] swap(vec[--j], vec[index]);//从右侧交换过来后，index要重新比较，因为不能确定交换过来的值与temp关系 } quik(vec, L, i); quik(vec, j, R); } int main() { vector<int> vec = { 7,3,0,9,4,2,2,6,5 }; quik(vec, 0, vec.size() - 1); for (auto it : vec) cout << it << " "; return 0; }完整递归版本（三色旗+两次递归）
代码示例：
void quik(vector<int>& vec, int L, int R) { int temp = 1; // 基准值设为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]); } } 以下是完整代码：
#include<iostream> #include<vector> using namespace std; void quik(vector<int>& vec, int L, int R) { int temp = 1; int i = L - 1; int j = R + 1; int index = L; while (index < j) { if (temp == vec[index]) index++; //和左侧交换 直接index++,因为左侧比较完，交换过来的值一定是temp else if (temp > vec[index]) swap(vec[++i], vec[index++]);//i右移之后和index交换，再index++ else//temp < vec[index] swap(vec[--j], vec[index]);//从右侧交换过来后，index要重新比较，因为不能确定交换过来的值与temp关系 } } int main() { vector<int> vec = { 1,0,2,0,1,1,2,0 }; quik(vec, 0, vec.size() - 1); for (auto it : vec) cout << it << " "; return 0; }三色旗分区版本
七、归并排序
归并排序是一种分治算法，基于二分法将序列递归分割，然后合并有序子序列。您的代码包括二分查找基础示例和归并排序实现。
- 问题背景：二分查找是归并排序的灵感来源，用于在有序序列中高效定位元素。
- 时间复杂度：O(\log n)，因为每次比较将搜索范围减半。
- 算法步骤：
- 初始化指针：
L（左边界）、R（右边界）。 - 循环：计算中点
mid，比较目标值与vec[mid]。- 如果
target < vec[mid]，则R = mid - 1。 - 如果
target > vec[mid]，则L = mid + 1。 - 如果相等，则返回元素。
- 如果
- 初始化指针：
- 算法原理：递归将序列分为两半，排序子序列后合并。核心：合并过程，确保有序性。
- 时间复杂度：O(n \log n)，因为分割和合并各需O(\log n)层，每层O(n)工作。
- 空间复杂度：O(n)，由于需要辅助数组存储合并结果。
- 稳定性：稳定，因为合并时相同元素保持相对顺序（代码中使用
<=比较）。 - 算法步骤：
- 分割：递归调用
MergeSort将序列分为左右子序列。 - 合并：使用辅助数组比较左右子序列元素，按序合并。
- 初始化指针：
i（左子序列起始）、j（右子序列起始）。 - 循环比较元素，放入辅助数组。
- 处理剩余元素。
- 将辅助数组复制回原序列。
- 初始化指针：
- 分割：递归调用
代码示例：
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); } 以下是完整代码：
#include<iostream> #include<vector> using namespace std; void Merge(vector<int>& vec, int L,int mid,int R) { //申请一个辅助数组大小：R-L+1 vector<int>temp(R - L + 1); int i = L; int j = mid + 1; int index = 0; //利用while循环比较两个有序数组L到mid和mid+1到R while (i <= mid && j <= R) { if (vec[i] <= vec[j]) { temp[index++] = vec[i++]; } else { temp[index++] = vec[j++]; } } //经历上一个步骤一定会有剩余元素，利用两个while循环判断 while (i <= mid)//左半边有剩余 { temp[index++] = vec[i++]; } while (j <= R)//右半边有剩余 { temp[index++] = vec[j++]; } //将辅助数组中元素还原到原数组，对应L到R的位置 index = L; for (int i = 0; i < temp.size(); i++) { vec[index++] = temp[i]; } } 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 << " ";//1 2 2 3 4 5 7 7 8 9 } return 0; }归并排序算法
示例代码：
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; } 以下是完整代码：
#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; }二分法基础
八、整体比较与总结
时间复杂度对比
- 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) | 不稳定 | 范围小的整数数据 |
通过对比可见，不同排序算法在时间、空间、稳定性上各有优劣，实际选择需结合数据规模、分布特征及稳定性需求。
