学步园

选择排序（Selection Sort）

算法核心思想：每一趟在n-i+1（i>=1）个记录中选取关键字最小的记录作为序列中的第i个记录

简单选择操作：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之，先看一个依选择排序思想的代码：

int SelectSort(MergeType *L)
{
	int min = 0;
	if (!L->elem)
	{
		return -1;
	}

	/*比较次数为：n-1+n-2 + 1 + 0 = n*(n-1)/2*/
	for (int i = 0; i < L->len-1; i++) //每一个数
	{
		min = i;
		for (int j = i+1; j < L->len; j++) //每一个数
		{
			if (L->elem[j] < L->elem[i])
			{
				min = j;
				//swap(L->elem[i], L->elem[j]);
			}
		}
		swap(L->elem[i], L->elem[min]);
	}
	return 0;
}

这里每次选择最小的放在第i趟的第i个位置上，这里从哪里选择，就是从i~len-1里选择最小的，看一个简单的实例

...
for (int i=0; i<L.len-1; i++)
{
	j = SelectMin(L,i);
	if(i != j)
	{ 
		L.elem[i]<-->L.elem[j]
	}
}
...

这里i != j是为了避免交换自己，看一下时间复杂度：最坏情况下比较的次数 =（n-1）+（n-2）+……+ 1 + 0 = n*（n-1）/ 2  = O(n^2)

这里看一下冒泡算法的for循环的特别之处

	for (i = 0; i <= L->len-1; i++)  //每一趟
	{ 	
		for (j = 0; j < L->len-1-i; j++) //每一个数
		{
			if (L->elem[j+1] < L->elem[j])
			{
				SWAP(L->elem[j+1], L->elem[j] );	
			}
		}	
	}

冒泡是在一趟里面比较数将最大的数沉入最低端；而选择排序是在对每一个数与其他的数进行比较，比较出最小的一个或者最大的一个，但是也是从一趟中选择最大的一个，是不是有点类似，看for循环后面的注释，只是for循环的含义不一样