排序算法是计算机科学中最基础也是最重要的内容之一。本文将带你系统学习常见排序算法，从原理到实现，并提供完整的C++代码示例。
一、排序算法概述
排序算法是将一组数据按照特定顺序（升序或降序）重新排列的过程。根据时间复杂度，排序算法可分为：
O(n²)级别：冒泡排序、选择排序、插入排序
O(n log n)级别：快速排序、归并排序、堆排序
O(n)级别：计数排序、桶排序、基数排序（线性排序，有特定限制）
本文将重点讲解前两类算法，并提供完整的C++实现。
二、冒泡排序（Bubble Sort）
算法原理
冒泡排序通过重复遍历数组，比较相邻元素，如果顺序错误就交换它们。每次遍历会将未排序部分的最大元素"冒泡"到正确位置。
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
// 优化：设置标志位，如果一轮没有交换说明已有序
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// 没有交换发生，提前结束
if (!swapped) break;
}
}
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
cout << "冒泡排序结果: ";
for (int num : arr) cout << num << " ";
return 0;
}
复杂度分析
时间复杂度：
最优情况：O(n)（已排序数组）
最差情况：O(n²)（逆序数组）
空间复杂度：O(1)（原地排序）
稳定性：稳定（相同元素不交换）
三、选择排序（Selection Sort）
算法原理
选择排序每次从未排序部分选择最小（或最大）元素，放到已排序序列的末尾。
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr[i], arr[min_idx]);
}
}
// 主函数中调用
vector<int> arr2 = {64, 25, 12, 22, 11};
selectionSort(arr2);
cout << "选择排序结果: ";
for (int num : arr2) cout << num << " ";
复杂度分析
时间复杂度：O(n²)（任何情况）
空间复杂度：O(1)
稳定性：不稳定（可能改变相同元素顺序）
四、插入排序（Insertion Sort）
算法原理
插入排序将数组分为已排序和未排序两部分，每次从未排序部分取一个元素插入到已排序部分的正确位置。
void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将比key大的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 主函数中调用
vector<int> arr3 = {12, 11, 13, 5, 6};
insertionSort(arr3);
cout << "插入排序结果: ";
for (int num : arr3) cout << num << " ";
复杂度分析
时间复杂度：
最优情况：O(n)（已排序数组）
最差情况：O(n²)（逆序数组）
空间复杂度：O(1)
稳定性：稳定
五、希尔排序（Shell Sort）
算法原理
希尔排序是插入排序的改进版，通过将数组分组进行插入排序，逐步减小分组间隔，最终完成排序。
void shellSort(vector<int>& arr) {
int n = arr.size();
// 初始间隔为n/2，逐步缩小
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
// 主函数中调用
vector<int> arr4 = {9, 8, 7, 6, 5, 4, 3, 2, 1};
shellSort(arr4);
cout << "希尔排序结果: ";
for (int num : arr4) cout << num << " ";
复杂度分析
时间复杂度：O(n log n) 到 O(n²)（取决于间隔序列）
空间复杂度：O(1)
稳定性：不稳定
六、归并排序（Merge Sort）
算法原理
归并排序采用分治策略：
将数组分成两半
递归地对两半进行排序
合并两个已排序的子数组
// 合并两个有序数组
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1), R(n2);
// 复制数据到临时数组
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 合并临时数组回原数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // 排序左半部分
mergeSort(arr, mid + 1, right); // 排序右半部分
merge(arr, left, mid, right); // 合并
}
}
// 主函数中调用
vector<int> arr5 = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr5, 0, arr5.size() - 1);
cout << "归并排序结果: ";
for (int num : arr5) cout << num << " ";
复杂度分析
时间复杂度：O(n log n)（所有情况）
空间复杂度：O(n)（需要临时数组）
稳定性：稳定
七、快速排序（Quick Sort）
算法原理
快速排序使用分治策略：
选择基准元素（pivot）
将数组分为两部分：小于基准和大于基准
递归地对两部分进行排序
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // 小于基准的边界
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 分区索引
quickSort(arr, low, pi - 1); // 排序左半部分
quickSort(arr, pi + 1, high); // 排序右半部分
}
}
// 主函数中调用
vector<int> arr6 = {10, 7, 8, 9, 1, 5};
quickSort(arr6, 0, arr6.size() - 1);
cout << "快速排序结果: ";
for (int num : arr6) cout << num << " ";
复杂度分析
时间复杂度：
平均情况：O(n log n)
最坏情况：O(n²)（当数组已排序或逆序时）
空间复杂度：O(log n)（递归调用栈）
稳定性：不稳定
八、算法比较与总结
排序算法 |
平均时间复杂度 |
最好情况 |
最坏情况 |
空间复杂度 |
稳定性 |
冒泡排序 |
O(n²) |
O(n) |
O(n²) |
O(1) |
稳定 |
选择排序 |
O(n²) |
O(n²) |
O(n²) |
O(1) |
不稳定 |
插入排序 |
O(n²) |
O(n) |
O(n²) |
O(1) |
稳定 |
希尔排序 |
O(n log n) |
O(n log²n) |
O(n²) |
O(1) |
不稳定 |
归并排序 |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
稳定 |
快速排序 |
O(n log n) |
O(n log n) |
O(n²) |
O(log n) |
不稳定 |
九、如何选择合适的排序算法
小规模数据：插入排序（实现简单，常数因子小）
中等规模数据：希尔排序（比插入排序更高效）
大规模数据：
需要稳定排序：归并排序
不需要稳定排序：快速排序（通常最快）
内存受限环境：堆排序（空间复杂度O(1)）
数据基本有序：插入排序或冒泡排序
在C++标准库中，std::sort()函数通常使用快速排序的优化版本（IntroSort），它会根据数据大小和递归深度自动切换排序算法。
掌握这些基础排序算法不仅有助于理解算法设计思想，也为学习更复杂的算法打下坚实基础。建议读者动手实现每种算法，并通过不同数据集观察它们的性能差异。