《掌握C++中的常用排序算法》
排序算法是计算机科学中的基础核心内容，广泛应用于数据处理、搜索优化、数据库操作等领域。在C++语言中，掌握常用排序算法不仅有助于提升编程效率，还能深入理解算法设计与时间复杂度分析。本文将系统介绍冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序六种经典算法的实现原理、代码实现及性能对比，帮助读者构建完整的排序算法知识体系。
一、基础排序算法
1.1 冒泡排序（Bubble Sort）
冒泡排序通过重复遍历待排序序列，比较相邻元素并交换顺序错误的元素对，使较大元素逐渐"浮"至序列末端。其时间复杂度为O(n²)，空间复杂度为O(1)，属于稳定排序算法。
void bubbleSort(int arr[], int n) {
for (int i = 0; i arr[j+1]) {
swap(arr[j], arr[j+1]);
swapped = true;
}
}
if (!swapped) break; // 提前终止优化
}
}优化后的版本通过添加交换标志位，可在最佳情况（已有序）下达到O(n)时间复杂度。
1.2 选择排序（Selection Sort）
选择排序每次遍历未排序部分，找到最小元素并与当前位置交换。该算法同样具有O(n²)时间复杂度，但交换次数少于冒泡排序。
void selectionSort(int arr[], int n) {
for (int i = 0; i 选择排序的缺点是每次交换可能破坏原有顺序，属于不稳定排序。
1.3 插入排序（Insertion Sort）
插入排序通过构建有序序列，逐个将未排序元素插入到正确位置。对于小规模数据或基本有序的数据效率较高。
void insertionSort(int arr[], int n) {
for (int i = 1; i = 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}插入排序在最佳情况（已有序）下时间复杂度为O(n)，最差情况为O(n²)。
二、高效排序算法
2.1 快速排序（Quick Sort）
快速排序采用分治策略，通过选取基准元素将数组分为两部分，递归排序子数组。平均时间复杂度为O(n log n)，最坏情况为O(n²)。
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j 优化策略包括三数取中法选择基准、小数组切换插入排序等。
2.2 归并排序（Merge Sort）
归并排序通过递归将数组分成两半，分别排序后合并。该算法稳定且时间复杂度恒为O(n log n)，但需要O(n)额外空间。
void merge(int arr[], int l, int m, int r) {
int n1 = m-l+1, n2 = r-m;
int L[n1], R[n2];
for (int i=0; i2.3 堆排序（Heap Sort）
堆排序利用二叉堆数据结构，先将数组构建成最大堆，然后重复取出堆顶元素并调整堆。
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2*i+1;
int right = 2*i+2;
if (left arr[largest]) largest = left;
if (right arr[largest]) largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
for (int i = n-1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}堆排序的时间复杂度恒为O(n log n)，且不需要额外存储空间。
三、STL排序算法
C++标准模板库提供了高效的排序函数：
#include
#include
bool compare(int a, int b) {
return a > b; // 降序排序
}
int main() {
std::vector v = {5, 2, 9, 1, 5};
// 升序排序
std::sort(v.begin(), v.end());
// 降序排序
std::sort(v.begin(), v.end(), compare);
// 自定义对象排序
struct Person {
std::string name;
int age;
};
std::vector people;
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
return a.age STL的sort函数通常采用内省排序（Introsort），结合了快速排序、堆排序和插入排序的优点。
四、性能对比与选择建议
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | 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) | 不稳定 |
选择建议：
- 小规模数据（n
- 基本有序数据：插入排序
- 通用排序：快速排序（需优化）或STL sort
- 需要稳定排序：归并排序
- 内存受限环境：堆排序
五、实际应用案例
案例1：学生成绩排序
struct Student {
string name;
int score;
int id;
};
bool compareStudents(const Student& a, const Student& b) {
if (a.score != b.score) return a.score > b.score;
return a.id & students) {
std::sort(students.begin(), students.end(), compareStudents);
}案例2：处理大数据流
#include
#include
struct MedianFinder {
priority_queue maxHeap; // 存储较小半部分
priority_queue, greater> minHeap; // 存储较大半部分
void addNum(int num) {
maxHeap.push(num);
minHeap.push(maxHeap.top());
maxHeap.pop();
if (maxHeap.size() minHeap.size()) return maxHeap.top();
return (maxHeap.top() + minHeap.top()) / 2.0;
}
}; 关键词：C++、排序算法、冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、STL排序、时间复杂度、稳定性
简介：本文系统介绍了C++中六种常用排序算法的实现原理与代码实践，包括冒泡排序、选择排序等基础算法和快速排序、归并排序等高效算法，分析了各算法的时间复杂度、空间复杂度及稳定性特征，提供了STL排序函数的使用方法，并通过实际案例展示排序算法的应用场景，帮助读者全面掌握C++排序技术。
