Java教程

【算法基础】关于冒泡,我们来排个序

本文主要是介绍【算法基础】关于冒泡,我们来排个序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

写在前面

一首《海阔天空》送给所有在外求学的游子。“今天我,寒夜里看雪飘过~~~”那么请问如何让大小不一的雪有顺序的排列呢?额,是不是有点扯远了……嗯,下面开始我们今天的学(zhuang)习(bi)计划……

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

 

 

 

 

 

1.     冒泡排序的基本原理

2.     实现的具体代码

3.     冒泡排序的缺陷

 

 

 

在我们初学者编程过程中,常常会遇到需要对一组无序的数据进行排序的问题,使之成为按从小到大或从大到小有序排列的数据。例如小程序中求一组数中最值,那么,有没有一些快速有效的方法能让我们更好的装个B呢?答案是有的!

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

01

冒泡排序的基本原理

还是先来看一个小问题,对以下这组数据进行从小到大排列:

10  2  3  19  60  12

 

这时候可能有按耐不住的小伙伴要say something了,我就观察这组数,发现2最小,就把2放最左;60最大,就放到最右;类似的把剩下的数也这样处理不就行了吗?

 

emmm……蛋是,如果给你100个数字,10000个数字呢?你要观察到什么时候?所以,这种活,还是给computer来做吧~

 

在这里有请我们的主角冒泡排序(掌声在哪里?)登场。

 

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

基本原理:从数据最左边开始将相邻两数进行两两比较,然后将较小的数放在左边,较大的数放在右边(即交换两个数的位置,较大的数像一个泡泡一样往上升),依次下去,这组数据的最大值就到了最右边,但剩下的数据还是杂乱,所以还必须对剩下的数据按刚才的方法再来排序;那么就可以得到了从小到大排列的数据。细心的读者从以上描述中可能会发现我们将用到两个for循环的嵌套。(类似的从大到小的排列也是可以实现的)

还是结合上面的例子给大家分步讲解一下吧~

①首先将10和2比较,因为10<2,所以数组变为

    2  10  3  19  60  12

②然后将10和3比较,因为10>3,所以数组变为

    2  3  10  19  60  12

 

③接着将10和19比较,因为10<19,所以数组不变 

    2  3  10  19  60  12

④将19和60比较,因为19<60,所以数组还是不变   

    2  3  10  19  60  12

⑤最后将60和12比较,因为60>12,所以第一次全部相邻比较的结果得到最大值60

 

第一次将最后两个数比较完之后数组变为 2  3  10  19  12  60

 

接下来对剩下的 2  3  10  19  12 进行相同的操作就得到了 

 2  3  10  12  19  60

 

开不开心?惊不惊喜?刺不刺激?



 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

代码实现

02

#include<stdio.h>

int swap(int *p, int *q);           //交换比较的两个数 

int main()

{

    int i, j, len, a[100];

    

    printf("please input the length!");//输入你想排序的数据的个数 

    scanf("%d", &len);

    printf("please input the integers you want to sort:\n");

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

    {

        scanf("%d", &a[i]);         //一个个输入你想排列的数据

    }

    

    for (i = 1; i <= len; ++i)         //第一个for循环表示要求多少数据的最大值 

    {

        for (j = 0; j < len - i; ++j)    //第二个for循环表示每求一次数据的最大值的过程 

        {

            if (a[j] > a[j + 1])

            swap(&a[j], &a[j + 1]);    //降序该如何实现? 

        }

    }

    for (j = 0; j < len; ++j)

    {

        printf("  %d", a[j]);

    }

      return 0;

}

 

int swap(int *p, int *q)

{

    int temp;

 

    temp = *p;

    *p = *q;

    *q = temp;

}

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

运行结果

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

03

冒泡排序的缺陷

由具体代码我们可以看出:

对n个数的排列,其最坏的情况是倒叙,为此要作n(n-1)/2次交换和比较;最好的情况是顺序,也要做n-1次比较;因此其排序的效率其实并不算高,而且他解决的数据规模也比较小,但作为入门的基础排序方法 其中体现的交换比较思想还是值得大家去思考的。读者可以思考一下,在冒泡排序的基础上是否可以改进一下,例如已经有一定顺序的片段是不是就可以看作一个整体而减少其比较和交换的次数呢?

 

好了,最后安利一波广告:你的支持便是我们最大的动力,快扫码关注我们程序猿声吧!

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

END

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

编辑 /华南理工大学本科一年级@李锐标

排版 /华中科技大学本科一年级@邓发珩

 

如有疑问,欢迎咨询:李锐标 (联系方式:2961347734@qq.com 公众号:程序猿声)

 

 

 

 

这篇关于【算法基础】关于冒泡,我们来排个序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!