前言
本文介绍一种经典排序算法——选择排序，是入门级的排序算法之一。以下是本篇文章正文内容，包括算法简介、算法特点、算法实现和C++示例。
一、选择排序简介
选择排序法也是枚举法的一种应用，就是反复从未排序的数列中选最大或最小的元素，加入另一个数列中，最后的结果就是已排序好的数列。原理就是不停扫描，每扫描一次，将最大值或者最小值放在首位。例如，n个数据选最小的放在第一个位置，再将剩下的n-1个数据选最小的放在第二个位置，以此类推执行n-1次扫描，就完成排序了。和冒泡排序异曲同工，因此都是入门的简单排序算法。
二、算法特点
1）无论是最坏、最好还是平均情况，都要执行n-1次扫描，所以时间复杂度为O(n2)。
2）由于冒泡为相邻两个数据相互比较而后决定是否互换位置，并不会改变原来排序的顺序，因此属于稳定排序法。
3）只需要一个额外空间，空间复杂度很低。
4）此排序法适用于数据量小或有部分数据已经排序过的情况。
三、代码实现
// 选择排序 vector<int> SelectSort(vector<int> data) { // 拷贝 vector<int> result = data; // 排序过程：必定扫描n-1次，n为数据个数 int size = static_cast<int>(data.size()); for (int t = 0; t < size - 1; ++t) { for (int i = t + 1; i < size; ++i) { if (result[t] > result[i]) { int temp = result[t]; result[t] = result[i]; result[i] = temp; } } } return result; }
四、C++示例
#include <iostream> #include <iomanip> #include <vector> #include <string> using namespace std; // 展示当前顺序 void Show(vector<int> data) { size_t size = data.size(); for (size_t i = 0; i < size; ++i) cout << setw(4) << data[i]; cout << endl; } // 选择排序 vector<int> SelectSort(vector<int> data) { // 拷贝 vector<int> result = data; cout << "选择排序：\n原始数据：\n"; Show(result); // 排序过程：必定扫描n-1次，n为数据个数 int size = static_cast<int>(data.size()); for (int t = 0; t < size - 1; ++t) { for (int i = t + 1; i < size; ++i) { if (result[t] > result[i]) { int temp = result[t]; result[t] = result[i]; result[i] = temp; } } cout << "第" << t + 1 << "次排序结果：\n"; Show(result); } cout << "排序后结果：\n"; Show(result); return result; } // 主函数 int main() { vector<int> data = { 9,11,567,0,-2,4,2 }; // 选择排序 vector<int> result2 = SelectSort(data); system("pause"); return 0; }
效果图：
综上可看出，选择排序每次将最小的值放在前方，也是比较基础的排序算法。优点是好理解，缺点emm不稳、速度超慢emmm
如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！
