冒泡排序：
从第一个元素开始，相邻元素之间进行比较，如果是逆序则交换位置，如果数组大小为n，那么第一趟要进行n-1次比较，这次比较后，最大或最小元素被置底(被置底的元素就没必要参加接下来的比较了)；第二趟从第一个元素开始到第n-1个元素，相邻元素之间两两比较，共进行n-2次，这些数中的最大或最小元素被置倒数第二层；以此类推，共经过n-1趟排序后，完成排序。因为该过程像水泡往水面冒，所以取名为冒泡排序。
冒泡排序实现(由小到大)：
#include
int main ()
{
int a[10];
int i,j,t;
printf("please enter 10 numbers:\n");
for(i=0; i<10; i++)
{
scanf("%d",&a[i]);
}
printf("\n");
for(j=0; j<9; j++)
{
for(i=0; i<9-j; i++)
{
if(a[i] > a[i+1])
{
t = a[i];
a[i] = a[i+1];
a[i+1] = t;
}
}
}
printf("the sorted numbers:\n");
for(i=0; i<10; i++)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
顾程序思其义：
(1)第一个for循环是控制循环次数，程序中是实现9趟循环。
(2)第二个for循环是控制每趟循环中进行9-j次比较。
但是这样的代码风格，我们一般不提倡，因为当所有的代码都写进了主函数，包括函数功能实现的那段，那么主函数看起来肯定显得很“臃肿”，所以我们提供了下面的一种方法，用函数实现功能，最后在主函数中输出我们想要的结果：
#include
#include
void my_maopao(int *p,int len)
{
assert(p);
int i,tmp;
int j;
for(i=0; i
{
for(j=0; j
{
if(*(p+j) > *(p+j+1))
{
tmp = *(p+j);
*(p+j) = *(p+j+1);
*(p+j+1) = tmp;
}
}
}
}
int main ()
{
int i;
int a[10];
int n = sizeof(a)/sizeof(a[0]-1);
printf("please enter 10 numbers:\n");
for(i=0; i
{
scanf("%d",&a[i]);
}
my_maopao(a,n);
printf("the sorted numbers:\n");
for(i=0; i
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
当然，在主函数中加入了一些语句，比如：
printf("please enter 10 numbers:\n");
printf("the sorted numbers:\n");
这些都是为了方便编译时输入数据而增加的提示语句，如果你觉得添加了它们而使主函数看起来也显得”臃肿“，那么你可以选择不添加，也不会影响结果的。
对比上面程序，我们检查下列程序：
#include
int main ()
{
int a[10];
int i = 0;
int j = 0;
int t;
printf("please enter 10 numbers:\n");
for(i=0; i<10; i++)
{
scanf("%d",&a[i]);
}
printf("\n");
for(i=0; i<9; i++)
{
for(; j<9-i; j++)
{
if(a[j] > a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
printf("the sorted numbers:\n");
for(i=0; i<10; i++)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
当我们上机运行检查结果时：
我们发现结果只进行一趟比较，就输出结果了。我们仔细看下面的for循环：
for(i=0; i<9; i++)
{
for(; j<9-i; j++)
{
if(a[j] > a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
问题就出在这里，第一趟比较是i=0，j=0,1,2,3,4,5,6,7,8，最后把9交换到了最后一个数；第二趟比较是i=1，j的值却为8，因为j在第二趟比较中并没有进行初始化为0！所以每一次进入循环j都没有初始化。固然就没有比较其他的数。所以第二个for循环一定要给j初始化，即：
for(i=0; i<9; i++)
{
for(j=0; j<9-i; j++)
{
if(a[j] > a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
选择排序：
假设有n个元素，首先通过n-1次比较，从n个数中找出最大或最小的元素， 将它与第一个数交换，将它置于第一个元素位置上；再从第二个数开始，通过n-2次比较，从剩余的n-1个数中找出最大或最小的元素，将它与第二个数交换，将它置于第二个元素位置上；重复上述过程，共经过n-1趟排序后，排序结束。
选择排序实现(由小到大)：
#include
int main ()
{
int i,j,k,t;
int a[10];
int n = sizeof(a)/sizeof(a[0]-1);
printf("please enter 10 numbers:\n");
for(i=0; i
{
scanf("%d",&a[i]);
}
for(i=0; i
{
k = i;
for(j=i+1; j
{
if(a[k]>a[j])
{
k = j;
}
if(k != i)
{
t = a[i];
a[i] = a[k];
a[k] = t;
}
}
}
printf("the sorted numbers:\n");
for(i=0; i
{
printf("%d ",a[i]);
}
return 0;
}
总结：
冒泡排序理论的计算量为n(n-1)/2；选择排序的计算量与冒泡排序相同；不过因为冒泡排序有元素交换操作，而选择排序没有，所以理论上选择要比排序速度快些。
