冒泡排序法(C语言)

冒泡排序:相邻两个数两两比较,小的数向前移(上浮),大的数向后移(下沉),如同水中的泡泡上浮一般;

冒泡排序图示:

如果有N个数,则要跑N-1次比较(每跑一次比较就会有一个较大数“沉底”),交换两个数的次数会随着跑的次数越来越多而变少。

C语言代码:

#include<stdio.h>

int main()

{

        int a[5]={4,3,1,6,0};

        int t,i,j;

        for(i=0;i<5-1;i++)//要跑5-1次

        {

                for(j=0;j<5-i-1;j++)//5-i-1中的减1是为了防止数组越界

                {

                        if(a[j]<a[j+1])//改变大于小于号可以实现升序排序(>)或降序排序 (<)

                        {

                                t=a[j];

                                a[j]=a[j+1];

                                a[j+1]=t;

                        }

                }

        }

        for(i=0;i<5;i++)

        {

                printf("%d\t",a[i]);

         }

return 0;

}

但是上述代码有一个缺点,如果要比较5个数(1,-1,8,4,2)会发现当跑第二次的时候数列已经有序了,剩下的第三次和第四次是可以不用跑的,是多余的。对代码进行优化,这样可以节省运行时间。

例子:

原始数组:1,-1,8,4,2

(1)-1,1,4,2,8

(2)-1,1,2,4,8

(3)-1,1,2,4,8

(4)-1,1,2,4,8

从上面看出从跑第3次时就已经没有两个数交换了(说明此时数组已经有序了),因此我们可以设置一个bool变量用来检测是否发生两个数的交换,如果没有则说明数组已经有序了,可以跳出循环了。

优化后的代码如下:

#include<stdio.h>

#include<stdbool.h>

int main()

{

        int a[5]={4,3,1,6,0};

        int t,i,j;

        for(i=0;i<5-1;i++)//要跑5-1次

        {

                bool swapped=false;//假设没有元素交换

                for(j=0;j<5-i-1;j++)//5-i-1中的减1是为了防止数组越界

                {

                            if(a[j]<a[j+1])//改变大于小于号可以实现升序排序(>)或降序排序 (<)

                            {

                                    t=a[j];

                                    a[j]=a[j+1];

                                    a[j+1]=t;

                                    swapped=true;


                            }

                }

                if(!swapped)//没有元素交换,数组已有序

                {

                        break;

                }

        }

        for(i=0;i<5;i++)

        {

                printf("%d\t",a[i]);

         }

return 0;

}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容