算法讲解
思路
选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：
初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；
然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，
从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
时间复杂度为O(n^2)，空间复杂度为O(1)
cpp代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//选择排序，每次找到最小值，放在前面的位置
void selectSort1(vector<int>& arr) {
int n = arr.size();
if (n <= 1) return;
int minIndex = 0;
for (int i = 0; i < n - 1; ++i) {
minIndex = i; //保存最小值的下标
for (int j = i + 1; j < n; ++j) { //找到最小值对应的下标
if (arr[minIndex] > arr[j])
minIndex = j;
}
swap(arr[i], arr[minIndex]); //将找到的最小值放到排好序的数组的下一个位置
}
}
//选择排序的改进：以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
void selectSort2(vector<int>& arr) {
int n = arr.size();
if (n <= 1) return;
int begin = 0; //参与单趟排序的第一个数的下标
int end = n - 1; //参与单趟排序的最后一个数的下标
while (begin < end) {
int maxi = begin;//保存当前此轮排序的最大值的下标
int mini = begin;//保存当前此轮排序的最小值的下标
//找到最大值和最小值的下标
for (int i = begin; i <= end; ++i) {
if (arr[i] < arr[mini])
mini = i;
if (arr[i] > arr[maxi])
maxi = i;
}
//最小值放在当前排序序列的开头
swap(arr[begin], arr[mini]);
//下面if判断的作用：防止最大的数在begin位置被换走
//如果最大值索引是begin，则经过上面这行代码之后，begin指向的值是最小值而不是最大值了，
//这种情况下，mini指向的才是最大值(因为交换过了)，所以需要从新更新最大值的索引
if (maxi == begin)
maxi = mini;
//最大值放在当前排序序列的结尾
swap(arr[maxi], arr[end]);
//更新单趟排序的两个端点位置
++begin;
--end;
}
}
int main() {
vector<int> arr = {6,4,3,7,1,9,5,8,2,10};
cout << "排序前： ";
for (int i = 0; i < 10; i++)
cout << arr[i] << " ";
cout << endl;
//selectSort1(arr);
selectSort2(arr);
cout << "排序后： ";
for (int i = 0; i < 10; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
结果：
