专栏首页海天一树小朋友学十大排序算法(1):冒泡排序

小朋友学十大排序算法(1):冒泡排序

一、基本原理(由小到大)

将相邻两个数比较,将大的调到后头。如果有n个数,则要进行n-1趟比较。 在第1趟中要进行n-1次两两比较,在第j趟比较中要进行n-j次两两比较。

1.png

上图中有5个数,要进行5 - 1 = 4趟比较。 第1趟,要进行n - 1 = 4次两两比较; 第2趟,要进行5 - 2 = 3次两两比较; 第3趟,要进行5 - 3 = 2次两两比较; 第4趟,要进行5 - 4 = 1次两两比较。

二、代码实现

#include <stdio.h>

// 打印数组,方便观察结果
void print_array(int a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// 冒泡排序算法
void bubble_sort(int a[], int n)
{
    // j表示第几轮比较
    for(int j = 0; j < n - 1; j++)
    {
        // i表示待比较的第几个元素
        for(int i = 0; i < n - 1 - j; i++)
        {
            if(a[i] > a[i+1])
            {
                a[i] ^= a[i+1];
                a[i+1] ^= a[i];
                a[i] ^= a[i+1];
            }

            // 打印每一轮比较,每次交换后的结果
            print_array(a, n);
        } 
        printf("********************\n");
    }
} 

int main ()
{
    int a[] = {5, 4, 3, 2, 1};
    int count = sizeof(a) / sizeof(int); // 求数组元素个数
    bubble_sort(a, count);

    return 0;
}

分析: bubble_sort函数中,有两层循环。外层用j来自增,内层用i来自增。 外层的循环自增的慢,内层的循环自增的快。 内层的循环i要都自增完,外层的j才会自加1。

执行过程为: j = 0, i = 0, if(a[0] > a[1])为真,a[0]与a[1]交换,数组变为{4,5,3,2,1} j = 0, i = 1, if(a[1] > a[2])为真,a[1]与a[2]交换,数组变为{4,3,5,2,1} j = 0, i = 2, if为真,a[2]与a[3]交换,数组变为{4, 3, 2, 5, 1} j = 0, i = 3, if为真,a[3]与a[4]交换,数组变为{4, 3, 2, 1, 5}, 此时最大的5已经挪到最后的位置,接下来5就不用再处理。

j = 1, i = 0, if为真,a[0]与a[1]交换,数组变为{3, 4, 2, 1, 5} j = 1, i = 1, if为真,a[1]与a[2]交换,数组变为{3, 2, 4, 1, 5} j = 1, i = 2, if为真,a[2]与a[3]交换,数组变为{3, 2, 1, 4, 5}, 此时4已经挪到倒数第二个位置,接下来4和5就不用再处理。

j = 2, i = 0, if为真,a[0]与a[1]交换,数组变为{2, 3, 1, 4, 5} j = 2, i = 1, if为真,a[1]与a[2]交换,数组变为{2, 1, 3, 4, 5}, 此时3已经挪到倒数第三个位置,接下来3、4和5就不用再处理。

j = 3, i = 0, if为真,a[0]与a[1]交换,数组变为{1, 2, 3, 4, 5}, 此时2已经挪到倒数第四个位置,接下来2、3、4和5就不用再处理。 剩余一个数1,也不用交换了。至此排序完毕。

输出结果:

4 5 3 2 1 
4 3 5 2 1 
4 3 2 5 1 
4 3 2 1 5 
********************
3 4 2 1 5 
3 2 4 1 5 
3 2 1 4 5 
********************
2 3 1 4 5 
2 1 3 4 5 
********************
1 2 3 4 5 
********************

三、时间复杂度

以{5,4,3,2,1}为例。 第1趟,要进行n - 1 = 4次两两比较; 第2趟,要进行5 - 2 = 3次两两比较; 第3趟,要进行5 - 3 = 2次两两比较; 第4趟,要进行5 - 4 = 1次两两比较。 总共比较了4 + 3 + 2 + 1 = 10次。 如果是n个数,比较的次数为(n - 1) + (n - 2) + … + 2 + 1 = n(n - 1) / 2次。所以时间复杂度是O(n2)。

四、稳定性

若排序的过程中,两个相同的数据,其先后顺序不会发生变化,则称这种排序方法是稳定的,否则就是不稳定的。 以对{5,2,2,1}进行冒泡排序为例。这个数列里有两个2,排序过程为: 5,2,2,1 2,5,2,1 2,2,5,1 2,2,1,5 2,2,1,5 2,1,2,5 1,2,2,5 从整个过程可以看出,两个2的相对一直都保持不变,所以,冒泡排序是稳定的排序算法。 后面的课程中,会接触到不稳定的排序算法。

本文分享自微信公众号 - KidsCode少儿编程(gh_de7b45c40e8b)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 小朋友学C语言(26):冒泡排序

    (一)基本原理(由小到大): 将相邻两个数比较,将大的调到后头。如果有n个数,则要进行n-1趟比较。 在第1趟中要进行n-1次两两比较,在第j趟比较中要进行n-...

    海天一树
  • 图的深度优先搜索

    图有两种最基本的搜索算法,一种是深度优先搜索,另一种是广度优先搜索。本节先介绍深度优先搜索。

    海天一树
  • Codeforces 977D 题解报告

    http://codeforces.com/contest/977/problem/D

    海天一树
  • VS 2017打开老项目报错:Project Target Framework Not Installed

    由于笔记本硬盘转速太慢,把光驱拆了,装了一个光驱位硬盘支架,搞了块250G的三星SSD固态硬盘,然后使用Samsung Data Migration,花了近2个...

    崔文远TroyCui
  • ElasticSearch命令执行漏洞:通过perl进行反弹shell

    我是攻城师
  • cf314E. Sereja and Squares(dp)

    给你一个擦去了部分左括号和全部右括号的括号序列,括号有25种,用除x之外的小写字母a~z表示。求有多少种合法的括号序列。答案对4294967296取模。 合法序...

    attack
  • 文字识别刷新世界纪录,海康威视浦世亮新智元“AI春节”解密安防大数据 | 新智元峰会演讲

    【新智元导读】在3月27日举行的中国“AI春节”——2017新智元开源·生态AI技术峰会上,海康威视研究院院长浦世亮发表演讲《安防大数据驱动下的智慧生活》,介绍...

    新智元
  • Java中的>>,>>>和<<

    我们都知道对于有符号数据类型,二进制最左端的数字为符号位,0代表正,1代表负,这里先介绍几个概念

    Java识堂
  • 动态 | 李飞飞高徒Andrej Karpathy加入特斯拉,网友:我可以相信自动驾驶了

    AI 科技评论按:据Techcrunch最新报道,特斯拉刚刚将OpenAI中的一员大将纳入麾下,担任人工智能与自动驾驶视觉部门主管。他就是Andrej Karp...

    AI科技评论
  • Node.js开发人员都应该知道的12个有用的包

    NPM 包节省了我们大量的时间和精力。需要日期库吗?NPM 上有一个包。需要实用程序库吗?没问题,只需安装一个软件包即可。每当你需要解决某个代码问题时,很可能会...

    深度学习与Python

扫码关注云+社区

领取腾讯云代金券