C++学习：六个月从基础到就业——STL算法（二）排序与变序算法
本文是我C++学习之旅系列的第二十六篇技术文章，也是第二阶段"C++进阶特性"的第四篇，主要介绍C++ STL算法库中的排序和变序算法。查看完整系列目录了解更多内容。
目录
引言
在上一篇文章中，我们介绍了STL算法库的基本概念以及查找类算法。本文作为系列的第二篇，将重点探讨STL算法库中的排序和变序算法，这些算法对于数据处理和分析至关重要。
排序是计算机科学中最基础也是最常用的操作之一，STL提供了多种高效且灵活的排序算法实现。而变序算法则用于改变容器中元素的顺序，如反转、旋转或随机打乱。
本文将详细介绍这些算法的用法、特性和应用场景，同时提供实际的代码示例，帮助你更好地理解和应用这些强大的工具。
排序算法详解
STL提供了多种排序算法，每种算法都有其特定的用途和优势。
std::sort：通用排序
std::sort是STL中最常用的排序算法，它实现了一种高效的快速排序（通常是内省排序，结合了快速排序、堆排序和插入排序的优点）。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
struct Person {
std::string name;
int age;
Person(std::string n, int a) : name(std::move(n)), age(a) {}
};
bool compareAge(const Person& a, const Person& b) {
return a.age < b.age;
}
int main() {
// 基本类型排序
std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
// 升序排序（默认）
std::sort(numbers.begin(), numbers.end());
std::cout << "升序排序结果: ";
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << std::endl;
// 降序排序
std::sort(numbers.begin(), numbers.end(), std::greater<int>());
std::cout << "降序排序结果: ";
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << std::endl;
// 自定义对象排序
std::vector<Person> people = {
{"Alice", 30},
{"Bob", 25},
{"Charlie", 35},
{"David", 28}
};
// 使用函数指针比较
std::sort(people.begin(), people.end(), compareAge);
std::cout << "\n按年龄排序的人员列表:" << std::endl;
for (const auto& p : people) {
std::cout << p.name << ": " << p.age << "岁" << std::endl;
}
// 使用lambda表达式按名字排序
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
return a.name < b.name;
});
std::cout << "\n按名字排序的人员列表:" << std::endl;
for (const auto& p : people) {
std::cout << p.name << ": " << p.age << "岁" << std::endl;
}
// 部分排序 - 只排序前半部分
std::vector<int> partialNumbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
std::sort(partialNumbers.begin(), partialNumbers.begin() + partialNumbers.size()/2);
std::cout << "\n部分排序结果: ";
for (int n : partialNumbers) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
}
输出：
升序排序结果: 1 2 3 4 5 6 7 8 9
降序排序结果: 9 8 7 6 5 4 3 2 1
按年龄排序的人员列表:
Bob: 25岁
David: 28岁
Alice: 30岁
Charlie: 35岁
按名字排序的人员列表:
Alice: 30岁
Bob: 25岁
Charlie: 35岁
David: 28岁
部分排序结果: 1 2 5 8 9 3 7 4 6
std::sort的主要特点：
- 要求随机访问迭代器：只能用于支持随机访问迭代器的容器（如vector、array和deque），不能用于list或关联容器
- 不稳定排序：不保证相等元素的相对顺序保持不变
- 复杂度：平均和最坏情况下都是O(n log n)
- 原地排序：不需要额外空间
std::stable_sort：稳定排序
当需要保持相等元素的原始相对顺序时，应该使用std::stable_sort：
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
struct Student {
std::string name;
int score;
Student(std::string n, int s) : name(std::move(n)), score(s) {}
// 用于输出
friend std::ostream& operator<<(std::ostream& os, const Student& s) {
return os << s.name << "(" << s.score << ")";
}
};
int main() {
// 创建一些学生成绩
std::vector<Student> students = {
{"Alice", 85},
{"Bob", 92},
{"Charlie", 85}, // 注意Charlie和Alice分数相同
{"David", 78},
{"Eve", 92} // 注意Eve和Bob分数相同
};
// 按分数排序（使用不稳定的std::sort）
std::vector<Student> studentsUnstable = students;
std::sort(studentsUnstable.begin(), studentsUnstable.end(),
[](const Student& a, const Student& b) {
return a.score > b.score; // 按分数降序
});
std::cout << "使用std::sort排序后（不稳定）:" << std::endl;
for (const auto& s : studentsUnstable) {
std::cout << s << " ";
}
std::cout << std::endl;
// 按分数排序（使用稳定的std::stable_sort）
std::vector<Student> studentsStable = students;
std::stable_sort(studentsStable.begin(), studentsStable.end(),
[](const Student& a, const Student& b) {
return a.score > b.score; // 按分数降序
});
std::cout << "使用std::stable_sort排序后（稳定）:" << std::endl;
for (const auto& s : studentsStable) {
std::cout << s << " ";
}
std::cout << std::endl;
return 0;
}
输出（可能因实现而异，因为sort的不稳定性）：
使用std::sort排序后（不稳定）:
Bob(92) Eve(92) Alice(85) Charlie(85) David(78)
使用std::stable_sort排序后（稳定）:
Bob(92) Eve(92) Alice(85) Charlie(85) David(78)
注意：虽然在这个简单的例子中，不稳定排序的输出可能与稳定排序相同，但在实际应用中，当数据集较大且有更多相等元素时，差异会更明显。
std::stable_sort的主要特点：
- 稳定性：保证相等元素的相对顺序不变
- 复杂度：如果有足够的额外内存，是O(n log n)，否则是O(n log^2 n)
- 额外空间：通常需要额外的内存空间
std::partial_sort：部分排序
当只需要排序前N个元素时，std::partial_sort更加高效：
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int main() {
std::vector<int> numbers = {9, 8, 7, 6, 5, 4, 3, 2, 1};
// 只排序前5个元素
std::partial_sort(numbers.begin(), numbers.begin() + 5, numbers.end());
std::cout << "部分排序后: ";
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << std::endl;
// 复制版本 - 不修改原始数据
std::vector<int> original = {9, 8, 7, 6, 5, 4, 3, 2, 1};
std::vector<int> partial(5); // 注意：需要预先分配空间
std::partial_sort_copy(original.begin(), original.end(),
partial.begin(), partial.end());
std::cout << "原始数据: ";
for (int n : original) {
std::cout << n << " ";
}
std::cout << std::endl;
std::cout << "复制的部分排序: ";
for (int n : partial) {
std::cout << n << " ";
}
std::cout << std::endl;
// 实际应用：获取前N名
std::vector<std::pair<std::string, int>> scores = {
{"Alice", 85},
{"Bob", 92},
{"Charlie", 78},
{"David", 95},
{"Eve", 88},
{"Frank", 70},
{"Grace", 82},
{"Hannah", 90}
};
// 获取前3名
std::partial_sort(scores.begin(), scores.begin() + 3, scores.end(),
[](const auto& a, const auto& b) {
return a.second > b.second; // 按分数降序
});
std::cout << "\n前三名:" << std::endl;
for (int i = 0; i < 3; ++i) {
std::cout << i+1 << ". " << scores[i].first
<< " - " << scores[i].second << "分" << std::endl;
}
return 0;
}
输出：
部分排序后: 1 2 3 4 5 9 8 7 6
原始数据: 9 8 7 6 5 4 3 2 1
复制的部分排序: 1 2 3 4 5
前三名:
1. David - 95分
2. Bob - 92分
3. Hannah - 90分
std::partial_sort的主要特点：
- 效率：当n << N（排序的元素数远小于总元素数）时，比完全排序更高效
- 复杂度：O(N log n)，其中N是总元素数，n是要排序的元素数
- 应用场景：常用于获取"前N名"或"最大/小的N个元素"
std::nth_element：定位第N个元素
std::nth_element算法重新排列元素，使得指定位置的元素位于排序后它应该在的位置，且它之前的所有元素都不大于它，之后的所有元素都不小于它。
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // for iota
int main() {
std::vector<int> numbers(10);
std::iota(numbers.begin(), numbers.end(), 1); // 填充1到10
// 随机打乱
std::random_shuffle(numbers.begin(), numbers.end());
std::cout << "打乱后: ";
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << std::endl;
// 找到中位数位置
size_t middle = numbers.size() / 2;
std::nth_element(numbers.begin(), numbers.begin() + middle, numbers.end());
std::cout << "第" << middle+1 << "个元素（中位数）: " << numbers[middle] << std::endl;
std::cout << "重排后: ";
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << std::endl;
// 查找第3小的元素
std::vector<int> data = {9, 7, 3, 5, 1, 8, 2, 6, 4};
std::nth_element(data.begin(), data.begin() + 2, data.end());
std::cout << "\n第3小的元素: " << data[2] << std::endl;
std::cout << "前3小的元素: ";
for (int i = 0; i < 3; ++i) {
std::cout << data[i] << " ";
}
std::cout << std::endl;
// 查找第3大的元素
std::vector<int> data2 = {9, 7, 3, 5, 1, 8, 2, 6, 4};
std::nth_element(data2.begin(), data2.begin() + 2, data2.end(), std::greater<int>());
std::cout << "第3大的元素: " << data2[2] << std::endl;
std::cout << "前3大的元素: ";
for (int i = 0; i < 3; ++i) {
std::cout << data2[i] << " ";
}
std::cout << std::endl;
return 0;
}
输出：
打乱后: 8 5 10 1 6 4 2 9 7 3
第5个元素（中位数）: 5
重排后: 1 2 4 3 5 6 7 9 10 8
第3小的元素: 3
前3小的元素: 1 2 3
第3大的元素: 7
前3大的元素: 9 8 7
std::nth_element的主要特点：
- 快速定位：可以快速找到序列中第n小（或大）的元素
- 复杂度：平均情况下是O(N)，其中N是元素总数
- 应用场景：计算中位数、分位数或选择前N大/小的元素
std::is_sorted 和 std::is_sorted_until：检查排序状态
这些算法用于检查容器是否已排序：
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int main() {
std::vector<int> sorted = {1, 2, 3, 4, 5};
std::vector<int> partially = {1, 2, 5, 3, 4};
std::vector<int> descending = {5, 4, 3, 2, 1};
// 检查是否已排序
bool is_sorted1 = std::is_sorted(sorted.begin(), sorted.end());
bool is_sorted2 = std::is_sorted(partially.begin(), partially.end());
std::cout << "sorted是否已排序: " << (is_sorted1 ? "是" : "否") << std::endl;
std::cout << "partially是否已排序: " << (is_sorted2 ? "是" : "否") << std::endl;
// 带谓词的排序检查
bool is_desc_sorted = std::is_sorted(descending.begin(), descending.end(),
std::greater<int>());
std::cout << "descending是否已降序排序: " << (is_desc_sorted ? "是" : "否") << std::endl;
// 查找第一个不排序的位置
auto it = std::is_sorted_until(partially.begin(), partially.end());
if (it != partially.end()) {
std::cout << "partially中第一个不排序元素的位置: "
<< (it - partially.begin())
<< "，值为: " << *it << std::endl;
}
// 实际应用 - 仅在未排序时排序
std::vector<int> data = {1, 3, 5, 7, 9, 2, 4, 6, 8};
std::cout << "\n排序前: ";
for (int n : data) {
std::cout << n << " ";
}
std::cout << std::endl;
// 查找排序终止位置
auto sortedUntil = std::is_sorted_until(data.begin(), data.end());
// 仅在未排序时排序
if (sortedUntil != data.end()) {
std::cout << "数据已排序直到位置: " << (sortedUntil - data.begin()) << std::endl;
// 只对后半部分排序，然后合并
std::sort(sortedUntil, data.end());
std::inplace_merge(data.begin(), sortedUntil, data.end());
}
std::cout << "排序后: ";
for (int n : data) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
}
输出：
sorted是否已排序: 是
partially是否已排序: 否
descending是否已降序排序: 是
partially中第一个不排序元素的位置: 2，值为: 5
排序前: 1 3 5 7 9 2 4 6 8
数据已排序直到位置: 5
排序后: 1 2 3 4 5 6 7 8 9
std::is_sorted和std::is_sorted_until对于优化排序操作和诊断排序问题非常有用。
二分查找算法
二分查找算法用于在已排序的范围内快速查找元素。
std::binary_search、std::lower_bound和std::upper_bound
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int main() {
std::vector<int> sorted = {1, 3, 3, 5, 7, 9, 9, 11, 13};
// 二分查找 - 检查元素是否存在
bool has3 = std::binary_search(sorted.begin(), sorted.end(), 3);
bool has4 = std::binary_search(sorted.begin(), sorted.end(), 4);
std::cout << "数组中包含3? " << (has3 ? "是" : "否") << std::endl;
std::cout << "数组中包含4? " << (has4 ? "是" : "否") << std::endl;
// lower_bound - 找出第一个不小于值的位置
auto lower3 = std::lower_bound(sorted.begin(), sorted.end(), 3);
auto lower4 = std::lower_bound(sorted.begin(), sorted.end(), 4);
std::cout << "第一个不小于3的位置: " << (lower3 - sorted.begin())
<< "，值为: " << *lower3 << std::endl;
std::cout << "第一个不小于4的位置: " << (lower4 - sorted.begin())
<< "，值为: " << *lower4 << std::endl;
// upper_bound - 找出第一个大于值的位置
auto upper3 = std::upper_bound(sorted.begin(), sorted.end(), 3);
auto upper9 = std::upper_bound(sorted.begin(), sorted.end(), 9);
std::cout << "第一个大于3的位置: " << (upper3 - sorted.begin())
<< "，值为: " << *upper3 << std::endl;
std::cout << "第一个大于9的位置: " << (upper9 - sorted.begin())
<< "，值为: " << *upper9 << std::endl;
// equal_range - 同时获得lower_bound和upper_bound
auto range3 = std::equal_range(sorted.begin(), sorted.end(), 3);
auto range9 = std::equal_range(sorted.begin(), sorted.end(), 9);
std::cout << "\n值为3的范围: ["
<< (range3.first - sorted.begin()) << ", "
<< (range3.second - sorted.begin()) << ")"
<< "，包含 " << (range3.second - range3.first) << " 个元素" << std::endl;
std::cout << "值为9的范围: ["
<< (range9.first - sorted.begin()) << ", "
<< (range9.second - sorted.begin()) << ")"
<< "，包含 " << (range9.second - range9.first) << " 个元素" << std::endl;
// 实际应用 - 计算特定值的个数
int count9 = std::count(sorted.begin(), sorted.end(), 9);
int count9_v2 = range9.second - range9.first; // 使用二分搜索，更高效
std::cout << "\n使用count计算9的个数: " << count9 << std::endl;
std::cout << "使用equal_range计算9的个数: " << count9_v2 << std::endl;
// 在自定义对象中使用二分搜索
struct Person {
std::string name;
int age;
bool operator<(const Person& other) const {
return age < other.age; // 按年龄排序
}
};
std::vector<Person> people = {
{"Alice", 25},
{"Bob", 30},
{"Charlie", 30},
{"David", 35},
{"Eve", 40},
{"Frank", 40},
{"Grace", 45}
};
// 查找30岁的人
Person searchKey{"", 30};
auto personRange = std::equal_range(people.begin(), people.end(), searchKey);
std::cout << "\n30岁的人：" << std::endl;
for (auto it = personRange.first; it != personRange.second; ++it) {
std::cout << it->name << " (" << it->age << "岁)" << std::endl;
}
return 0;
}
输出：
数组中包含3? 是
数组中包含4? 否
第一个不小于3的位置: 1，值为: 3
第一个不小于4的位置: 3，值为: 5
第一个大于3的位置: 3，值为: 5
第一个大于9的位置: 7，值为: 11
值为3的范围: [1, 3)，包含 2 个元素
值为9的范围: [5, 7)，包含 2 个元素
使用count计算9的个数: 2
使用equal_range计算9的个数: 2
30岁的人：
Bob (30岁)
Charlie (30岁)
二分查找算法的主要特点：
- 前提条件：只能用于已排序的范围
- 复杂度：O(log n)，比线性搜索更高效
- 应用场景：
binary_search：检查元素是否存在lower_bound：查找不小于目标值的第一个位置upper_bound：查找大于目标值的第一个位置equal_range：查找等于目标值的范围
变序算法详解
变序算法改变元素的顺序而不改变元素本身的值。
std::reverse：反转元素顺序
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// 反转整个序列
std::reverse(numbers.begin(), numbers.end());
std::cout << "完全反转后: ";
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << std::endl;
// 反转部分序列
std::reverse(numbers.begin() + 2, numbers.begin() + 8);
std::cout << "部分反转后: ";
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << std::endl;
// 反转并复制到新容器
std::vector<int> original = {1, 2, 3, 4, 5};
std::vector<int> reversed(original.size());
std::reverse_copy(original.begin(), original.end(), reversed.begin());
std::cout << "\n原始容器: ";
for (int n : original) {
std::cout << n << " ";
}
std::cout << std::endl;
std::cout << "反转复制后的容器: ";
for (int n : reversed) {
std::cout << n << " ";
}
std::cout << std::endl;
// 反转字符串
std::string text = "Hello, World!";
std::reverse(text.begin(), text.end());
std::cout << "\n反转后的字符串: " << text << std::endl;
// 实际应用：单词反转但保持单词顺序
std::string sentence = "The quick brown fox jumps over the lazy dog";
std::string result;
result.reserve(sentence.size());
std::istringstream iss(sentence);
std::string word;
bool first = true;
while (iss >> word) {
if (!first) result += " ";
std::reverse(word.begin(), word.end());
result += word;
first = false;
}
std::cout << "原句: " << sentence << std::endl;
std::cout << "单词反转后: " << result << std::endl;
return 0;
}
输出：
完全反转后: 10 9 8 7 6 5 4 3 2 1
部分反转后: 10 9 3 4 5 6 7 8 2 1
原始容器: 1 2 3 4 5
反转复制后的容器: 5 4 3 2 1
反转后的字符串: !dlroW ,olleH
原句: The quick brown fox jumps over the lazy dog
单词反转后: ehT kciuq nworb xof spmuj revo eht yzal god
std::reverse的主要特点：
- 就地操作：直接在原始范围内改变元素顺序
- 复杂度：线性时间O(n)
- 常见应用：字符串反转、回文检查、数组反转等
std::rotate：旋转元素
std::rotate将范围内的元素循环移动，使得指定的中间元素成为新的开始。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
template<typename T>
void printVector(const std::vector<T>& vec, const std::string& name) {
std::cout << name << ": ";
for (const auto& item : vec) {
std::cout << item << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// 将第4个元素（下标3）旋转到开头
auto middle = numbers.begin() + 3; // 指向元素4
std::rotate(numbers.begin(), middle, numbers.end());
printVector(numbers, "左旋转后(4到开头)");
// 将倒数第4个元素（下标6）旋转到开头
std::vector<int> numbers2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
middle = numbers2.end() - 4; // 指向元素7
std::rotate(numbers2.begin(), middle, numbers2.end());
printVector(numbers2, "左旋转后(7到开头)");
// 将第1个元素（下标0）旋转到结尾（右旋转）
std::vector<int> numbers3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
middle = numbers3.begin() + 1; // 右旋转一次
std::rotate(numbers3.begin(), middle, numbers3.end());
printVector(numbers3, "右旋转后(1到结尾)");
// 旋转并复制到新容器
std::vector<int> original = {1, 2, 3, 4, 5};
std::vector<int> rotated(original.size());
std::rotate_copy(original.begin(), original.begin() + 2, original.end(),
rotated.begin());
printVector(original, "原始容器");
printVector(rotated, "旋转复制后的容器");
// 实际应用：循环移动字符串
std::string str = "abcdefg";
std::rotate(str.begin(), str.begin() + 2, str.end()); // 左移2个位置
std::cout << "\n左移2位后的字符串: " << str << std::endl;
// 循环左移k位实现
std::string original_str = "abcdefg";
int k = 3; // 移动k位
// 确保k在合理范围内
k %= original_str.size();
std::rotate(original_str.begin(), original_str.begin() + k, original_str.end());
std::cout << "左移" << k << "位后的字符串: " << original_str << std::endl;
return 0;
}
输出：
左旋转后(4到开头): 4 5 6 7 8 9 10 1 2 3
左旋转后(7到开头): 7 8 9 10 1 2 3 4 5 6
右旋转后(1到结尾): 2 3 4 5 6 7 8 9 10 1
原始容器: 1 2 3 4 5
旋转复制后的容器: 3 4 5 1 2
左移2位后的字符串: cdefgab
左移3位后的字符串: defgabc
std::rotate的主要特点：
- 效率：原地旋转，不需要额外空间
- 复杂度：对于双向迭代器是线性时间O(n)
- 常见应用：字符串/数组旋转、循环移位、排列生成等
std::shuffle 和 std::random_shuffle：随机打乱元素
这些算法用于将元素随机排列。注意：std::random_shuffle在C++17中已弃用，应使用std::shuffle。
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <string>
int main() {
std::vector<int> deck;
// 创建一副"扑克牌"
for (int i = 1; i <= 13; ++i) { // 1=A, 11=J, 12=Q, 13=K
for (int j = 0; j < 4; ++j) { // 四种花色
deck.push_back(i);
}
}
// 使用C++98/03风格的随机洗牌（弃用的方法，仅作为参考）
std::vector<int> deck1 = deck;
std::srand(std::time(nullptr)); // 设置随机种子
std::random_shuffle(deck1.begin(), deck1.end());
std::cout << "random_shuffle洗牌后(前10张): ";
for (int i = 0; i < 10; ++i) {
std::cout << deck1[i] << " ";
}
std::cout << std::endl;
// 使用现代C++风格的随机洗牌
std::vector<int> deck2 = deck;
// 创建随机数生成器
std::random_device rd;
std::mt19937 g(rd()); // 梅森旋转算法
std::shuffle(deck2.begin(), deck2.end(), g);
std::cout << "shuffle洗牌后(前10张): ";
for (int i = 0; i < 10; ++i) {
std::cout << deck2[i] << " ";
}
std::cout << std::endl;
// 实际应用：生成随机排列
std::vector<int> perm(10);
std::iota(perm.begin(), perm.end(), 0); // 填充0到9
std::shuffle(perm.begin(), perm.end(), g);
std::cout << "\n随机排列: ";
for (int n : perm) {
std::cout << n << " ";
}
std::cout << std::endl;
// 实际应用：随机选择样本
std::vector<std::string> population = {
"Alice", "Bob", "Charlie", "David", "Eve",
"Frank", "Grace", "Hannah", "Ian", "Julia"
};
// 随机打乱并选择前3个
std::shuffle(population.begin(), population.end(), g);
std::cout << "\n随机选择的3个样本: ";
for (int i = 0; i < 3; ++i) {
std::cout << population[i] << " ";
}
std::cout << std::endl;
return 0;
}
输出（因为是随机的，所以每次运行结果都会不同）：
random_shuffle洗牌后(前10张): 8 7 1 9 6 4 3 5 3 12
shuffle洗牌后(前10张): 8 13 13 7 5 8 12 10 2 10
随机排列: 6 2 3 9 4 5 0 8 7 1
随机选择的3个样本: Julia Hannah David
std::shuffle的主要特点：
- 均匀分布：使用现代随机数生成器提供更好的随机性
- 复杂度：线性时间O(n)
- 常见应用：洗牌、随机采样、蒙特卡洛模拟等
std::next_permutation 和 std::prev_permutation：排列生成
这些算法用于生成元素的所有可能排列：
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
void printPermutation(const std::string& perm, int count) {
std::cout << count << ": " << perm << std::endl;
}
int main() {
// 生成字符串的所有排列
std::string str = "ABC";
int count = 1;
std::cout << "所有 " << str << " 的排列:" << std::endl;
printPermutation(str, count++);
while (std::next_permutation(str.begin(), str.end())) {
printPermutation(str, count++);
}
// 生成数字的排列
std::vector<int> nums = {1, 2, 3};
std::cout << "\n所有 [1,2,3] 的排列:" << std::endl;
// 确保从第一个排列开始
std::sort(nums.begin(), nums.end());
count = 1;
do {
std::cout << count++ << ": ";
for (int n : nums) {
std::cout << n << " ";
}
std::cout << std::endl;
} while (std::next_permutation(nums.begin(), nums.end()));
// 生成前一个排列
std::string str2 = "CBA"; // 注意：从最大排列开始
std::cout << "\n所有 " << str2 << " 的前序排列:" << std::endl;
count = 1;
printPermutation(str2, count++);
while (std::prev_permutation(str2.begin(), str2.end())) {
printPermutation(str2, count++);
}
// 实际应用：解决排列问题
std::vector<std::string> people = {"Alice", "Bob", "Charlie"};
std::cout << "\n三人座位的所有可能安排:" << std::endl;
count = 1;
do {
std::cout << count++ << ": ";
for (const auto& person : people) {
std::cout << person << " ";
}
std::cout << std::endl;
} while (std::next_permutation(people.begin(), people.end()));
return 0;
}
输出：
所有 ABC 的排列:
1: ABC
2: ACB
3: BAC
4: BCA
5: CAB
6: CBA
所有 [1,2,3] 的排列:
1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1
所有 CBA 的前序排列:
1: CBA
2: CAB
3: BCA
4: BAC
5: ACB
6: ABC
三人座位的所有可能安排:
1: Alice Bob Charlie
2: Alice Charlie Bob
3: Bob Alice Charlie
4: Bob Charlie Alice
5: Charlie Alice Bob
6: Charlie Bob Alice
std::next_permutation和std::prev_permutation的主要特点：
- 完整性：可以生成所有可能的排列
- 字典序：生成的排列是字典序的
- 复杂度：单次操作是线性时间O(n)，生成所有排列是O(n!)
- 常见应用：排列问题、组合优化、穷举搜索等
实际应用案例
让我们通过一个更复杂的例子来说明如何结合使用多种排序和变序算法：
学生成绩管理系统
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <random>
#include <numeric>
// 学生信息结构
struct Student {
std::string id;
std::string name;
std::vector<int> scores; // 多门课程的分数
double average; // 平均分
// 计算平均分
void calculateAverage() {
if (scores.empty()) {
average = 0.0;
} else {
average = std::accumulate(scores.begin(), scores.end(), 0.0) / scores.size();
}
}
};
// 比较函数
bool compareByAverage(const Student& a, const Student& b) {
return a.average > b.average; // 降序排列
}
bool compareByName(const Student& a, const Student& b) {
return a.name < b.name; // 按姓名字典序
}
bool compareById(const Student& a, const Student& b) {
return a.id < b.id; // 按ID字典序
}
// 随机生成学生数据
std::vector<Student> generateRandomStudents(int n) {
std::vector<Student> students(n);
std::vector<std::string> firstNames = {"John", "Emma", "Michael", "Sophia", "William",
"Olivia", "James", "Ava", "Logan", "Isabella"};
std::vector<std::string> lastNames = {"Smith", "Johnson", "Williams", "Brown", "Jones",
"Garcia", "Miller", "Davis", "Rodriguez", "Martinez"};
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> firstNameDist(0, firstNames.size() - 1);
std::uniform_int_distribution<> lastNameDist(0, lastNames.size() - 1);
std::uniform_int_distribution<> scoreDist(50, 100);
for (int i = 0; i < n; ++i) {
students[i].id = "S" + std::to_string(10000 + i);
students[i].name = firstNames[firstNameDist(gen)] + " " + lastNames[lastNameDist(gen)];
// 生成3门课程的分数
students[i].scores.resize(3);
std::generate(students[i].scores.begin(), students[i].scores.end(),
[&]() { return scoreDist(gen); });
students[i].calculateAverage();
}
return students;
}
// 打印学生信息
void printStudents(const std::vector<Student>& students, int limit = -1) {
std::cout << std::left << std::setw(8) << "ID"
<< std::setw(20) << "Name"
<< std::setw(10) << "Average"
<< "Scores" << std::endl;
std::cout << std::string(50, '-') << std::endl;
int count = 0;
for (const auto& student : students) {
if (limit != -1 && count >= limit) break;
std::cout << std::left << std::setw(8) << student.id
<< std::setw(20) << student.name
<< std::fixed << std::setprecision(2) << std::setw(10) << student.average;
for (int score : student.scores) {
std::cout << score << " ";
}
std::cout << std::endl;
++count;
}
}
int main() {
// 生成20个随机学生
auto students = generateRandomStudents(20);
std::cout << "原始学生数据 (前10名):" << std::endl;
printStudents(students, 10);
// 按平均分排序（降序）
std::sort(students.begin(), students.end(), compareByAverage);
std::cout << "\n按平均分排序后 (前10名):" << std::endl;
printStudents(students, 10);
// 查找平均分超过85的学生数量
auto it = std::find_if(students.begin(), students.end(),
[](const Student& s) { return s.average < 85.0; });
int highScoreCount = std::distance(students.begin(), it);
std::cout << "\n平均分85分以上的学生数量: " << highScoreCount << std::endl;
// 按姓名排序
std::sort(students.begin(), students.end(), compareByName);
std::cout << "\n按姓名排序后 (前10名):" << std::endl;
printStudents(students, 10);
// 随机选择5名学生
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(students.begin(), students.end(), g);
std::cout << "\n随机选择的5名学生:" << std::endl;
printStudents(students, 5);
// 二分查找示例
// 首先按ID排序
std::sort(students.begin(), students.end(), compareById);
// 创建一个学生对象用于查找
Student searchStudent;
searchStudent.id = "S10010"; // 假设我们要找ID为S10010的学生
// 使用二分查找
auto foundIt = std::lower_bound(students.begin(), students.end(), searchStudent, compareById);
if (foundIt != students.end() && foundIt->id == searchStudent.id) {
std::cout << "\n找到ID为" << searchStudent.id << "的学生:" << std::endl;
std::cout << "姓名: " << foundIt->name << ", 平均分: " << foundIt->average << std::endl;
} else {
std::cout << "\n未找到ID为" << searchStudent.id << "的学生" << std::endl;
}
return 0;
}
这个例子展示了如何在一个学生成绩管理系统中结合使用多种排序和变序算法：
- 使用
std::sort按不同条件排序学生信息 - 使用
std::find_if查找满足特定条件的学生 - 使用
std::shuffle随机选择学生 - 使用
std::lower_bound进行二分查找特定ID的学生
总结
本文详细介绍了STL算法库中的排序和变序算法，这些算法为C++程序员提供了强大的数据处理工具。我们探讨了：
排序算法：
std::sort：通用快速排序std::stable_sort：稳定排序std::partial_sort：部分排序std::nth_element：定位第N个元素std::is_sorted和std::is_sorted_until：排序状态检查
二分查找算法：
std::binary_search：检查元素是否存在std::lower_bound和std::upper_bound：查找边界std::equal_range：查找等值范围
变序算法：
std::reverse：反转元素顺序std::rotate：旋转元素std::shuffle：随机打乱元素std::next_permutation和std::prev_permutation：生成排列
通过实例，我们展示了这些算法在实际应用中的用法，如数据排序、查找、随机采样和排列生成等。
掌握这些算法可以帮助你编写更简洁、高效的代码，并且避免重复发明轮子。在实际开发中，合理选择和组合这些算法可以大大提高程序的性能和可维护性。
在下一篇文章中，我们将继续探索STL算法库，重点介绍数值算法和集合算法，如std::accumulate、std::inner_product、std::set_union等。
参考资源
- C++ Reference - 详细的STL算法文档
- 《C++标准库》by Nicolai M. Josuttis
- 《Effective STL》by Scott Meyers
- 《C++17 STL Cookbook》by Jacek Galowicz
这是我C++学习之旅系列的第二十六篇技术文章。查看完整系列目录了解更多内容。
如有任何问题或建议，欢迎在评论区留言交流！