选择排序与冒泡排序的比较

选择排序（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;
}

...
for (int i=0; i
  
   L.elem[j]
	}
}
...
  

这里i != j是为了避免交换自己，这里看一下冒泡算法的for循环的特别之处

再看一下时间复杂度：最坏的情况比较的次数=（n-1）+（n-2）+……+1+0=n*（n-1）/ 2 =O(n^2)

	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] );	
			}
		}	
	}