有意思的算法(一)----冒泡排序-阿里云开发者社区

开发者社区> 令仔很忙> 正文

有意思的算法(一)----冒泡排序

简介: <div class="markdown_views"> <blockquote> <p>    <font size="3"><strong>冒泡排序的基本思想是:每次比较两个相邻的元素,如果它们的顺序错误就把他们交换过来。</strong></font></p> </blockquote> <p>    <font size="3">下面举一个具体的例子来介绍一下冒泡
+关注继续查看

    冒泡排序的基本思想是:每次比较两个相邻的元素,如果它们的顺序错误就把他们交换过来。

    下面举一个具体的例子来介绍一下冒泡排序。

这里写图片描述

    有12,35,99,18,76五个数进行从大到小的排序,既然是从大到小排序,也就是说越小的越靠后,可不要把这句当成废话,这可是最关键的地方!

    首先比较第1位和第2位的数字,第1位是12,第2位是35,12<35,根据越小的越靠后的原则,交换两个数,交换之后的顺序是:35,12,99,18,76。

    按照刚才的说法,依次比较第2位和第3位,第3位和第4位,第4位和第5位,结果分别如下:

12,35,99,18,76
35,12,99,18,76
35,99,12,18,76
35,99,18,12,76
35,99,18,76,12

    经过4次比较,最小的一个数已经就位了(注意12的移动过程),很有意思,咱们这么来看12的移动过程,看了下面的图片你就会更明白:

这里写图片描述

    整个过程就如同是一个气泡,一步一步往后“翻滚”,直到最后一位,所以这个排序有一个很好听的名字“冒泡排序”

    可以这么说,我们的排序只将5个书中最小的一个归位了,没将一个数归位我们称其为“一趟”

    下面接着上面的“第一趟”,开始“第二趟”,在第二趟中有一点需要注意的是,由于最小的一位已经归位了,我们只需要找出第二小的数来就可以了,也就是说在本趟中,只需比较到第3位和第4位就可以了,第5位已经是最小的了,就不需要比较了。

    “第三趟”的结果是:

99,76,35,18,12

    到了最后一趟“第四趟”。有的人就要问了,这还用比较么,这结果不已经出来了么?当然,这里纯属巧合,要是用别的数试一试可能就不是了。

冒泡排序的原理:每一趟只能确定将一个数归位。即第一趟只能将第末位(第5位)上的数归位,第二趟只能将倒数第2位上的数(第4位)归位,第三趟只能将倒数第3位上的数(第3位)归位,可是现在前面还有两个位置上的数没有归位,所以依然要进行“第四趟”

    下面咱们总结一下:如果有n个数进行排序,只需将n-1个数归位,也就是说要进行n-1趟操作。而“每一趟”都需要从第一位开始进行相邻的两个数的比较,将较小的一个数放在后面,比较完毕后诺以为继续比较下面两个相邻数的大小,重复此步骤,知道最后一个尚未归位的数,已经归位的书就不需要在进行比较了。

    下面是具体的实现代码:

#include <stdio.h>
int main()
{
    int a[100],i,j,t,n;
    scanf("%d",&n);  '''输入一个数n,表示接下来又n个数'''
    for(i=1;i<=n;i++)  '''循环读入n个数到数组a中'''
        scanf("%d",&a[i]);

    '''冒泡排序的核心部分'''
    for(i=1;i<=n-1;i++)    '''n个数排序,只用进行n-1趟'''
    {
        for(j=1;j<=n-i;j++)  '''从第1位开始比较知道最有一个尚未归位的数,想一想为什么到n-i就可以了'''
        {
            if(a[j]<a[j+1])   '''比较两个数的大小'''
            {t=a[j];a[j]=a[j+i];a[j+i]=t;}
        }
    }

    for(i=1;i<=n;i++)  '''输出结果'''
        printf("%d ",a[i]);

    getchar();getchar();
    return 0;
}

    冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是O(N2)

转载请注明出处:http://blog.csdn.net/zlts000/article/details/49515505

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9143 0
算法-冒泡排序及其效率
算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度)。 时间复杂度是指程序运行的速度。 空间复杂度是指一个算法所需要的额外的空间。
5 0
算法---冒泡排序法
冒泡排序: 通过对相邻元素的对比,并交换位置,一步一步的把一个元素给挑选出来。 我们可以使用两层嵌套的for循环来实现这个过程,也就是实现冒泡排序: //外层控制轮数 for(var i=0;i
1668 0
【算法导论】冒泡排序法
冒泡排序法 时间复杂度:O(n*n) 基本思想:从数组最后一个元素开始,依次与前一个元素比较,若比前一个元素小,则与之交换位置,然后再与当前前一个元素比较,直到遇到比它大的元素为止。
1188 0
算法笔记--冒泡排序
冒泡排序是一种选择排序,算法简单,在数据基本有序的情况下效率较高。 1. 算法思想           通过无序区中元素相邻元素的比较和交换,使最小的元素如同气泡一般浮动至顶端。 2. 时间复杂度           最好情况 O(n):序列正序有序,外循环只执行一次,内层比较n次,不需移动元素(针对改进版而言)          最坏情况 O(n^2):序列逆序有序,每次比较都需交换两个元素 3. 空间复杂度 O(1)           就地排序,辅助空间为常数级 4. 稳定性           稳定。
771 0
+关注
156
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载