在 C++ 中，排序算法可以通过标准库函数（如 std::sort）实现，也可以手动实现经典算法。以下是常见排序方法及其示例：
1. 使用标准库 std::sort
C++ 标准库 <algorithm> 提供了高效的 std::sort 函数，通常基于 内省排序（快速排序 + 堆排序的混合算法）。
示例代码：
#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> nums = {5, 2, 9, 1, 5, 6};// 默认升序排序std::sort(nums.begin(), nums.end());// 自定义排序（降序）std::sort(nums.begin(), nums.end(), [](int a, int b) {return a > b;});// 输出结果for (int num : nums) {std::cout << num << " ";}return 0;
}
2. 常见排序算法及手动实现
(1) 冒泡排序（Bubble Sort）
- 原理：重复交换相邻元素，将最大值“冒泡”到末尾。
- 时间复杂度：O(n²)（最坏和平均）
- 稳定性：稳定
void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {std::swap(arr[j], arr[j+1]);}}}
}
(2) 选择排序（Selection Sort）
- 原理：每次从未排序部分选择最小元素，放到已排序部分末尾。
- 时间复杂度：O(n²)
- 稳定性：不稳定
void selectionSort(int arr[], int n) {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;}}std::swap(arr[i], arr[min_idx]);}
}
(3) 插入排序（Insertion Sort）
- 原理：逐个将元素插入到已排序部分的正确位置。
- 时间复杂度：O(n²)（适用于小数据或接近有序数据）
- 稳定性：稳定
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i-1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}
(4) 快速排序（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 <= high-1; j++) {if (arr[j] < pivot) {i++;std::swap(arr[i], arr[j]);}}std::swap(arr[i+1], arr[high]);return i+1;
}void quickSort(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);}
}
(5) 归并排序（Merge Sort）
- 原理：分治法，将数组分为两半，分别排序后合并。
- 时间复杂度：O(n log n)
- 稳定性：稳定
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++) L[i] = arr[l+i];for (int j = 0; j < n2; j++) R[j] = arr[m+1+j];int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}void mergeSort(int arr[], int l, int r) {if (l >= r) return;int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);
}
3. 算法选择建议
- 小规模数据：插入排序（简单且稳定）。
- 大规模数据：优先使用
std::sort（高效且优化过）。 - 需要稳定性：归并排序或插入排序。
- 内存敏感：堆排序（O(1) 空间复杂度）。
总结
C++ 标准库的 std::sort 在大多数情况下是最优选择。手动实现排序算法有助于理解原理，但在实际开发中应优先使用标准库函数。
练习：
