信息学奥赛系列教程：选择排序

选择排序：

选择排序（Selection sort）是一种简单的排序算法。它的基本思想是每一次从待排序数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

如下图所示：对5,3,4,1,6,2进行排序，过程如下：

选择排序的代码实现：

#include <iostream>
using namespace std;
const int MAXN =10001; 
int main()
{
  int n,k,i,j;
  float temp,a[MAXN];
  cout<<"请输入排序个数:"<<endl;
  cin>>n;
  for (i=0;i<n;i++)
  {
	 cout<<"请输入第"<<i+1<<"个数:"<<endl;
	 cin>>a[i];
  }
  
  for (i=0;i<n;i++)
  {
	  	k=i;
	  	//遍历以后的各位数，与当前的数相比，找出最小的数的下标 
	  	for (j=i+1;j<n;j++)
	  	{
	  		if (a[j]<a[k])
	  		{
	  			k=j;  //数组元素的下标
	  		}	   
	  	}
	  	//交换，将最小的数移动到最前 
	    if (k!=i)
	    {
	    	temp=a[i];
	    	a[i]=a[k];
	    	a[k]=temp;
	    }
  } 
  for (i=0;i<n;i++)
  {
  	cout<<a[i]<<" ";
  }
  
}

选择排序的时间复杂度：

元素交换操作介于0到n-1之间,复杂度O(n)

比较操作，n(n-1)/2次,复杂度O(n2)

比较后的赋值操作：3(n-1),复杂度O(n)

选择排序的稳定性：

在一趟选择时，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了，选择排序是一种不稳定的排序。