冒泡排序和直接选择排序

#include<stdio.h>

int Array[100];

void SortArray(int Array[],int n)//小到大排，直接选择排序
{
	int i,j,t;
	for(i = 0; i < n-1; i++)
	{
		for(j = i+1; j < n; j++)
		{
			if(Array[i] > Array[j])
			{
				t = Array[j];
				Array[j] = Array[i];
				Array[i]=t;	
			}		
		}	
	}
}

void SortArray1(int Array[],int n)//小到大排，冒泡排序
{
	int i,t;
	for(i = 0; i < n-1; i++)
	{
		for(j = 0; j < n-i-1; j++)
		{
			if(Array[j] > Array[j+1])
			{
				t = Array[j];
				Array[j] = Array[j+1];
				Array[j+1]=t;	
			}		
		}	
	}
}
int main()
{
	int i,n;
	while(1)
	{
		printf("请输入一共要输入的数字数n：n");
		scanf("%d",&n);
		printf("请输入一串数字：n");
		for(i = 0; i < n; i++)
			scanf("%d",&Array[i]);
		SortArray1(Array,n);
		printf("输出从大到小的排序：n");
		for(i = 0; i < n; i++)
			printf("%3d",Array[i]);
		printf("nnn");	
	}

return 0;

}

SortArray这种是http://www.neu.edu.cn/cxsj/case/case7.html上面flash演示的（但代码不是，代码是相邻比较的冒泡排序）

这是直接选择排序法

　在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=1/2(n*n - n),

　　总的移动次数 3(n-1).由此可知，直接选择排序的时间复杂度为 O(n*n)，所以当记录占用字节数较多时，通常比直接插入排序的执行速度快些。

　　由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

?

SortArray1 这种是冒泡排序

若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次交换，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

?

直接选择排序法和冒泡排序都很相似，时间复杂度也是O(n*n)。