selectionSort
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
算法步骤
#include<iostream>
usingnamespacestd;
//选择排序，参数为数组和数组长度
voidselectionSort(intarr[],intn){
for(inti=0;i<n;i++){
//找到[i,n)范围内的最小值坐标，初始最小值坐标为i
intminIndex=i;
for(intj=i+1;j<n;j++){
if(arr[j]<arr[minIndex])
minIndex=j;
}
//交换坐标值
swap(arr[i],arr[minIndex]);
}
}
intmain(){
inta[10]={10,9,8,7,6,5,4,3,2,1};
selectionSort(a,10);
for(inti=0;i<10;i++)
cout<<a[i] <<" ";
cout<<endl;
return0;
}
//输出
//1 2 3 4 5 6 7 8 9 10
上述代码只能对int类型进行选择排序，设置为模板函数即可对任意类型进行排序：template<typename T>
//选择排序
template<typenameT>
voidselectionSort(Tarr[],intn){
for(inti=0;i<n;i++){
//找到[i,n)范围内的最小值坐标，初始最小值坐标为i
intminIndex=i;
for(intj=i+1;j<n;j++){
if(arr[j]<arr[minIndex])
minIndex=j;
}
//交换坐标值
swap(arr[i],arr[minIndex]);
}
}
操作符重载
当要对自定义的类或结构体进行选择排序时，就需要重构operator<，因为判断元素的大小是依靠操作符<。因为要输出，所以也要对输出操作符<<进行重载
//Student.h
#ifndef STUDENT_H
#define STUDENT_H
#include<iostream>
#include<string>
usingnamespacestd;
structStudent{
stringname;
intscore;
booloperator< (constStudent&otherStudent){
returnthis->score<otherStudent.score;
}
//重构operator<<
friendostream&operator<< (ostream&os,constStudent&student){
os<<"Student:"<<student.name<<" "<<student.score<<endl;
returnos;
}
};
#endif
//selectionSort.cpp
#include<iostream>
#include "Student.h"//引入Student.h
usingnamespacestd;
//选择排序
template<typenameT>
voidselectionSort(Tarr[],intn){
for(inti=0;i<n;i++){
//找到[i,n)范围内的最小值坐标，初始最小值坐标为i
intminIndex=i;
for(intj=i+1;j<n;j++){
if(arr[j]<arr[minIndex])
minIndex=j;
}
//交换坐标值
swap(arr[i],arr[minIndex]);
}
}
intmain(){
Studentd[4]={ {"D",90},{"C",100},{"B",95},{"A",95} };
selectionSort(d,4);
for(inti=0;i<4;i++)
cout<<d[i];
cout<<endl;
return0;
}
/*从小到大排序
Student:D 90
Student:B 95
Student:A 95
Student:C 100
*/
操作符本质上是函数，分为成员函数和全局函数
成员函数
去掉friend，那么operator <<变为成员函数，需要使用对象来调用，成员函数默认含有隐藏的参数this
this：是一个pointer（指针），指向函数调用者，即对象。（谁调用我，我就指向谁）
通过this指针获取对象中的成员，可以
this->name，也可以(*this).name，也可以name，因为this是可以省略的
// ostream& operator << (this,ostream& os)
// ||
ostream&operator<< (ostream&os){
os<<"Student:"<<this->name<<" "<<(*this).score<<endl;
returnos;
}
//d[i]为一个对象，对象调用operator<<函数，参数为cout
d[i].operator<<(cout);
同样的成员函数operator<，调用时arr[j]<arr[minIndex]=arr[j].operator<(arr[minIndex])，C++中操作符都是作用于左边
全局函数
友元函数operator <<不是成员函数，因此不需要对象来调用即可使用
friendostream&operator<< (ostream&os,constStudent&stu){
os<<"Student:"<<stu.name<<" "<<stu.score<<endl;
returnos;
}
//全局函数直接调用，参数为cout和Student的对象d[i]
operator<<(cout,d[i]);
//与下行代码效果相同
cout<<d[i];
