写好最简单的选择排序

选择排序，所有排序算法中最简单的一个，不是嘛，如果有哪本编程书中没有直接或者间接的含有这个算法，真的换一本吧:),在此仅以此博客记录一下，我所认识的选择排序。

选择排序，为什么取这个名？

之所以叫选择排序，是因为每次都是要从剩余的序列中选择一个最大(最小)的元素将其放在最终位置(有序时元素所在的位置)

选择排序的思路(从小到大排序)

1:从序列的第K+1个元素开始，找到序中最小的元素（K=0）

2:将最小的元素与第K个元素进行比较，如果比第K个元素小，则进行交换，否则不交换

3:从第K+1个元素开始，重复上述过程

时间复杂度

循环计算变量从0开始，则算法每次循环选择一个最小值均需要的比较次数为n-i-1,故总共的比较次数为n(n-1)/2,同时由于每次循环都有可能做交换操作，帮最多进行的交换操作次数为n-1次，帮时间复杂度为O(n^2)

空间复杂度

空间复杂度为0(1),需要一个交换变量，下面可以看到，可以连这1空间的变量都不需要，将代码一与代码三结合，但会影响效率

算法的稳定性

选择排序是不稳定的，你想想这样的一个序列5,5,2，从小往大排序好，第一5就在第二个5的后面，所以是不稳定的。

最容易想到的方法

void SelectSort(int *a ,int N)
{
	int temp;
	for(int i=0;i<N;i++)
		for(int j=i+1;j<N;j++)
		{
			if(a[i]>a[j])
			{
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
}

效率高一点的算法

void SelectSort(int *a ,int N)
{
	int tmp;
	for(int i=0;i<N;i++)
	{
		int min=i;
		for(int j=i+1;j<N;j++)
			if(a[j]<a[min])
				min=j;
		if(i!=min)
		{
			tmp=a[i];
			a[i]=a[min];
			a[min]=tmp;
		}
	}
}

效率再高一点的算法

void SelectSort(int *a ,int N)
{
	for(int i=0;i<N;i++)
	{
		int min=i;
		for(int j=i+1;j<N;j++)
			if(a[j]<a[min])
				min=j;
		if(i!=min)
		{
			a[i]=a[i]^a[min];
			a[min]=a[min]^a[i];
			a[i]=a[min]^a[i];
		}
	}
}