前言
上一篇写了关于桶排序的实现，简单回顾一下就是定义一个数组，将所有数组元素均初始化为 0，然后根据数组下标统计对应数字的个数，再依次输出数据。但是桶排序有许多限制，比如它所排序的必须是整数类型，而且浪费内存较多。所以的看情况使用。这一篇给大家介绍一个新的排序算法--冒泡排序。
正文
简单介绍一下，冒泡排序就是将一组数据逐个的进行比较，如果采取从小到大的方式进行排序，那么每当前一个数比后一个数大时则将两个数位置进行交换。直到这组数据排序结束。下面以一个例子进行说明。如给定一组数据 12 56 14 23 7 9，要求从小到大排序。
根据上面的说明，我们进行排序，首先我们比较 12 和 56 ，明显 12 小于 56 ，则它们位置不变，再比较 56 和 14 ，56 大于 14 ，则将两个数位置进行交换，以此类推，一遍比较下来的结果为 12 14 23 7 9 56 ，这里我们可以发现，一遍比较我们只用比较五次，所以可以得出，如果有 n 个数，我们一遍比较下来只需要比较 n-1 次。同时我们还可以发现一遍比较下来一定有一个数字待在了它最后应该待的地方，比如这一边比较后，最大的 56 待在了最后一个位置，那么此时也就只剩下五个数字处于无序状态。
根据我们前面得出的结论，下一遍我们只需要比较四次就可以了，推广开来，我们每一遍的比较次数依次递减，直到排序完成。根据这个规律，我们发现我们需要比较五遍，也就是从五递减到一需要的次数。当然我们会发现这里给出的数据不需要比较五遍就已经达到要求了，但并不是所有的一组数据都会如此，比如 9 8 7 6 5 4 ，就需要比较五遍。到此为止，我们已经得出了冒泡排序的过程。那么下面我们来写一段程序来测试我们的理论，看看结果是不是如我们所想的那样。
#include<stdio.h>
//Small to Big
int main()
{
int a[6] = {12,56,14,23,7,9},temp;
for(int i = 0;i < 5;i++)
{
for(int j = 0;j < 5 - i;j++)
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
printf("第%d遍比较后结果：\n",i+1);
for(int k = 0;k < 6;k++)
{
printf("%d\t",a[k]);
}
printf("\n");
}
printf("\n最后的排序结果：\n");
for(int k = 0;k < 6;k++)
{
printf("%d\t",a[k]);
}
getchar();
return 0;
}
运行结果
根据程序的运行结果，我们发现跟我们预料的一致，每一遍比较过后，一定会有一个数字归位。当然我们这里给出的是整数的排序，只是粗略说一下冒泡排序的概念，它的作用远远 不止这些，以后遇到了再进行一些补充吧。最后根据代码，我们可以得出冒泡排序的时间复杂度为 O（n2）,这应该就是冒泡排序的不足之处了，虽然比起桶排序，它的功能增加了，可是在时间复杂度上也是大大的增加了，那么有没有一种排序方式可以兼具两者的优点呢。当然有，下一篇我会给大家介绍，先留个悬念。
网友评论