1.简介

选择排序和冒泡排序非常接近，只是在冒泡排序的基础上做了小改进。在每一轮选择第 i 大的数字的时候，记录下第 i 大的数字的位置，最后做一次性的交换，减少了数据挪动的开销。

2.算法步骤

n 个数的排序，总体上分成了 n-1 个步骤（对应程序里面的第一轮循环）。对于第 i 个步骤而言，就是找出第 i 小的数，把这个数字最后交换到了下标 i 的位置。

在做第 i 步骤之前，第 1 大，第 2 大....，第 i-1 大的数字已经被找到，放在了有序的区域，所以，第 i 大的数只会出现在下标第 i+1 到 n 的范围内找。通过一层循环能确定其位置。

3.效果图

4.程序模板

4.1 不断选小的数字

#include<bits/stdc++.h>
using namespace std;
int x[10001];
int main(){
    int n,p,MIN;
    cin>>n;

    for(int i=1;i<=n;i++)
    	cin>>x[i]; //数字输入到 x 数组 ,一开始是无序的 

	//第 i 轮循环，要把第 i 小的数字交换到从前往后数的第 i 个位置 
	for(int i=1;i<n;i++)
	{
		p = i;  //先假定最小的数是 x[i];
		for(int j=i+1;j<=n;j++)
		{
			if(x[j]<x[p])
				p = j;
		}
		
		// x[p] 就是本轮循环里面最小的数 
		if(p!=i) swap(x[p],x[i]); 
	}
 
	for(int i=1;i<=n;i++) //输出有序的数字 
		cout<<x[i]<<" "; 
 
    return 0;
}

4.1 不断选大的数字

#include<bits/stdc++.h>
using namespace std;
int x[10001];
int main(){
    int n,p,MIN;
    cin>>n;

    for(int i=1;i<=n;i++)
    	cin>>x[i]; //数字输入到 x 数组 ,一开始是无序的 

	for(int i=n;i>1;i--)
	{
		p = i;  //先假定最大的数是 x[i];
		for(int j=1;j<i;j++)
		{
			if(x[j]>x[p])
				p = j;
		}
		
		// x[p] 就是本轮循环里面最大的数 
		if(p!=i) swap(x[p],x[i]); 
	}
 
	for(int i=1;i<=n;i++) //输出有序的数字 
		cout<<x[i]<<" "; 
 
    return 0;
}