排序是我们学习算法过程中重要且基础的一环，例如对下面的排序问题，我们应该怎么做呢？
排序问题
选择排序思想和实现思路
提到排序问题，很容易想到的思路就是找出来所有数据中最大（或最小）的元素，放在一个新列表的第一位，然后再在剩下的元素中找出最大（或最小）的元素，放在新列表的第二位，以此类推.....。这就是选择排序（selection sort）的算法思想。
快速排序思想
上图就是选择排序算法思想，但一个算法的实现往往不能通过一个简单的思想就搞定（这就是思想与现实的距离，哈哈~）。选择算法的实现并不会新建一个空白列表（因为这样太奢侈了），而是直接在原列表上进行操作：首先从列表中找出最大（或者最小）的元素，将其与列表中的第一个元素互换位置，然后再从剩余元素中挑选出最大（或者最小）的元素，将其与列表中的第二个元素交换位置。以此类推，直到剩余元素的个数为零。具体的实施步骤如下：
选择排序算法实现
算法实现
接下来我们看一下其具体的算法实现：
#include <iostream>
#include <vector>
using namespace std;
struct Student {
string name;
int score;
bool operator<(const Student& other) {
// 判断分数是否相同，不同就按照分数比较；如果相同，按名字比较大小
return score != other.score ? score < other.score : name < other.name;
}
friend ostream& operator<<(ostream& os, Student& s) {
os << s.name << " " << s.score << endl;
return os;
}
};
// 选择排序
template <typename T>
void selectionSort(vector<T>& vec) {
int size = vec.size();
for (int i = 0; i < size; i++) {
int maxValueIndex = i;
for (int j = i + 1; j < size; ++j) {
// 这里用来决定算法是升序还是降序
if (vec[maxValueIndex] < vec[j]) maxValueIndex = j;
}
swap(vec[i], vec[maxValueIndex]);
}
}
int main() {
vector<Student> students;
students.emplace_back(Student{"张三", 68});
students.emplace_back(Student{"李四", 79});
students.emplace_back(Student{"李飞", 98});
students.emplace_back(Student{"刘麻", 59});
cout << "\n---排序前---\n";
for (auto student : students) {
cout.width(8); // 设置数据宽度
cout << student;
}
// 选择排序
selectionSort(students);
cout << "\n---排序后---\n";
for (auto student : students) {
cout.width(8); // 设置数据宽度
cout << student;
}
return 0;
}
程序运行结果：
---排序前---
张三 68
李四 79
李飞 98
刘麻 59
---排序后---
李飞 98
李四 79
张三 68
刘麻 59
