C++作为一门高效的编程语言，其标准库提供了强大的排序功能，以下我们将探索一些C++中的经典排序技巧。
1. STL Sort函数
标准模板库（STL）中的 sort()函数是最常用的排序方法，它基于快速排序算法，但是会根据元素数量和数据分布适应性地采用插入排序或堆排序。
#include <algorithm>
#include <vector>
std::vector<int> nums = {4, 1, 3, 5, 2};
std::sort(nums.begin(), nums.end());
2. 自定义比较函数
可以自定义比较函数来实现特定的排序规则，此比较函数必须是一个返回bool类型的二元谓词。
#include <algorithm>
#include <vector>
bool compare(int a, int b) {
return a > b; // 降序排列
}
std::vector<int> nums = {4, 1, 3, 5, 2};
std::sort(nums.begin(), nums.end(), compare);
3. 使用Lambda表达式
C++11引入的Lambda表达式可以让你在调用 sort()时直接写内联比较逻辑，使代码更加紧凑。
#include <algorithm>
#include <vector>
std::vector<int> nums = {4, 1, 3, 5, 2};
std::sort(nums.begin(), nums.end(), [](int a, int b) {
return a < b; // 升序排列
});
4. 部分排序
STL中的 partial_sort可以对集合的一部分元素进行排序，其余元素未必保证有序。
#include <algorithm>
#include <vector>
std::vector<int> nums = {4, 1, 3, 5, 2};
std::partial_sort(nums.begin(), nums.begin() + 3, nums.end());
5. 稳定排序
stable_sort类似于 sort，区别在于它保持相等元素的相对顺序。这适用于保持多个字段的顺序排序。
#include <algorithm>
#include <vector>
std::vector<std::pair<int, char>> pairs = {
{1, 'A'}, {2, 'B'}, {1, 'B'}, {2, 'A'}};
std::stable_sort(pairs.begin(), pairs.end());
6. nth_element的使用
当你需要找到经过排序后会位于第n个位置的元素，而不需要对整个集合排序时，可以使用 nth_element。
#include <algorithm>
#include <vector>
std::vector<int> nums = {4, 1, 3, 5, 2};
std::nth_element(nums.begin(), nums.begin() + 2, nums.end());
7. 堆排序
使用STL中的 make_heap(), push_heap(), pop_heap()可以实现堆排序，适用于动态数据集合的高效排序。
#include <algorithm>
#include <vector>
std::vector<int> nums = {4, 1, 3, 5, 2};
std::make_heap(nums.begin(), nums.end());
std::sort_heap(nums.begin(), nums.end());
8. 插入排序
对于小型数据集或几乎排序好的数据集，插入排序是一个很好的选择，因为它有很低的开销。
#include <vector>
std::vector<int> nums = {4, 1, 3, 5, 2};
for (int i = 1; i < nums.size(); ++i) {
int key = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j = j - 1;
}
nums[j + 1] = key;
}
9. 快速排序
自己实现快速排序算法，可以更好地理解其分而治之的原理。
#include <vector>
int partition(std::vector<int>& nums, int low, int high) {
int pivot = nums[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (nums[j] < pivot) {
i++;
std::swap(nums[i], nums[j]);
}
}
std::swap(nums[i + 1], nums[high]);
return (i + 1);
}
void quickSort(std::vector<int>& nums, int low, int high) {
if (low < high) {
int pi = partition(nums, low, high);
quickSort(nums, low, pi - 1);
quickSort(nums, pi + 1, high);
}
}
结语
每种排序算法都有其适用场景，掌握这些排序技巧能让你在面对不同的排序需求时更加得心应手。实际编程中需权衡数据规模、排序算法的时间复杂度和稳定性来选用合适的排序算法。
