排序算法---选择排序

排序是我们学习算法过程中重要且基础的一环，例如对下面的排序问题，我们应该怎么做呢？

排序问题

选择排序思想和实现思路

提到排序问题，很容易想到的思路就是找出来所有数据中最大（或最小）的元素，放在一个新列表的第一位，然后再在剩下的元素中找出最大（或最小）的元素，放在新列表的第二位，以此类推.....。这就是选择排序（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