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);
}
}
结语
每种排序算法都有其适用场景,掌握这些排序技巧能让你在面对不同的排序需求时更加得心应手。实际编程中需权衡数据规模、排序算法的时间复杂度和稳定性来选用合适的排序算法。
云服务器/高防CDN推荐
蓝易云国内/海外高防云服务器推荐
海外免备案云服务器链接:www.tsyvps.com
蓝易云安全企业级高防CDN:www.tsycdn.com
持有增值电信营业许可证:B1-20222080【资质齐全】
蓝易云香港五网CN2 GIA/GT精品网络服务器。拒绝绕路,拒绝不稳定。