基本思想：
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
简单选择排序的示例：
操作方法：
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推.....
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。
算法实现：（杭电ACM 1040） 验证 结果AC啦
#include<iostream>
using namespace std;
const int N =;
void sort(int a[],int num);
void print(int a[],int num);
void swap(int &a,int &b);
int main()
{
int s[N];
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int j=;j<n;j++)
cin>>s[j];
sort(s,n);
print(s,n);
cout<<endl;
}
return ;
}
void sort(int a[],int num)//选择排序代码
{
for(int i=;i<num;i++)
{
int k=i;
for(int j=i+;j<num;j++)
{
if(a[k]>a[j])//从剩下的元素选择一个最小的元素
k=j;
}
if(k!=i)
{
swap(a[k],a[i]);//与最小的元素进行交换
} }
}
void swap(int &a,int& b)//交换元素
{
int temp;
temp=a;
a=b;
b=temp;
}
void print(int a[],int n)//输出数组元素
{
cout<<a[];
for(int k=;k<n;k++)
{
cout<<" "<<a[k];
}
}
简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：
#include<iostream>
using namespace std;
const int N =;
void SelectSort(int a[],int );
void print(int a[],int num);
void swap(int &a,int &b); int main()
{
int s[N];
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int j=;j<n;j++)
cin>>s[j];
SelectSort(s,n);
print(s,n);
cout<<endl;
}
return ;
}
void SelectSort(int arr[],int size)
{
int minIndex, maxIndex;
for (int i = ; i < size / ; i++) {
minIndex = i;
maxIndex = size-i-;
for (int j = i; j < size - i ; j++) { if (arr[j] > arr[maxIndex]) {
maxIndex = j;
//continue;
}
if (arr[j] < arr[minIndex]) {
minIndex = j; } }
if (maxIndex == i && minIndex == size - i - ) {
//特殊交换位置一，当最大的交换位置和最小的交换位置都在最前面和最后面
swap(arr[maxIndex],arr[minIndex]);
}
else if (maxIndex == i) {
//特殊交换位置二，当最大的交换位置是最前面
// Swap(arr[n - i], arr[maxIndex])
swap(arr[size-i-],arr[maxIndex]); swap(arr[i], arr[minIndex]);
}
else if (minIndex == size - i - ) {
//特殊交换位置三，当最小的交换位置是最后面
swap(arr[i], arr[minIndex]);
swap(arr[size - i-], arr[maxIndex]);
}
else {
//除了上面三种特殊交换，就剩普通交换了，普通交换随便哪个先交换都行
swap(arr[i], arr[minIndex]);
swap(arr[size - i-], arr[maxIndex]) ;
}
}
}
void swap(int &a,int& b)//交换元素
{
int temp;
temp=a;
a=b;
b=temp;
}
void print(int a[],int n)//输出数组元素
{
cout<<a[];
for(int k=;k<n;k++)
{
cout<<" "<<a[k];
}
}