一.原理
选择排序的原理非常简单，就是选出最小(大)的数放在第一位，在剩下的数中，选出最小(大)的数，放在第二位......重复上述步骤，直到最后一个数。
二.过程
原始数据
第一次排序，选出最小的数1，交换1与25的位置
第二次排序，选出剩下的数据中最小的数4，交换7与4的位置
重复以上过程，最后
三.代码
#include <iostream>
#include <vector> using namespace std; template <typename T>
void SelectSort( vector<T> &nums ){
int minIndex;
for( int i = 0; i < nums.size(); i++ ){
minIndex = i;
for( int j = i+1; j < nums.size(); j++ ){
if( nums[j] < nums[minIndex]){
minIndex = j;
}
}
swap(nums[i],nums[minIndex]);
}
} int main(){
vector<int> nums{25,7,37,47,13,13,30,15,4,1,12,49};
cout<<" Before Sort:" ;
for( auto m: nums){
cout << m <<" ";
}
cout<<endl;
SelectSort( nums );
cout<< " After Sort:";
for( auto m: nums){
cout << m <<" ";
}
cout<<endl;
}
四.总结
1.选择排序的交换操作节约0-n-1之间，比较操作为(n-1)+(n-1)....+2+1 = n(n-1)/2
2.对于最好的情况，已经有序，交换0次，对于最差情况，逆序，交换n-1次