你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

《算法零基础100讲》(第33讲) 排序入门 - 冒泡排序

2021-11-22 7:37:04

文章目录

  • 零、写在前面
  • 一、概念定义
  • 二、题目描述
  • 三、算法详解
  • 四、源码剖析
  • 五、推荐专栏
  • 六、粉丝福利

零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第三十三天了。
  每天打卡的题,做不出来没关系,因为困难的题涉及知识点较多,后面还是会开放出来的,就像昨天的 最大公约数 那道题今天还是会有,所以不要着急,内容能看懂,能自己分析,能做出简单题,就可以打卡。
  在刷题的过程中,总结自己遇到的坑点,写出 「 解题报告 」 供他人学习,也是一种自我学习的方式。这就是经典的帮助他人的同时,成就自己。目前, 「 万人千题 」 社区 每天都会有五六篇高质量的 「 解题报告 」 被我 「 加精 」。如果觉得自己有能力的,也可以来发布你的 「 解题报告 」。千万级流量,你我共同拥有。

一、概念定义

  排序问题是最经典的算法问题了,一般一开始学的算法就是排序。但是由于 C/C++ 都有现成的库函数(C里是 qsort、C++里是sort),所以导致很多人就没有学排序算法本身,其实排序算法的思路非常经典,从最简单的学起,对日后学习复杂算法是非常有帮助的。这就是举一反三,粗类旁通的道理。
  从今天开始,我们来试着掌握每个排序算法的思路,今天是冒泡排序。
  冒泡排序,我们把每个元素想象成一个一个水泡,大的往上冒,直到所有水泡都按照大小有序排列,如图所示:

图示含义
■ 的柱形代表尚未排好序的数
■ 的柱形代表正在执行比较的两个数
■ 的柱形代表已经排好序的数

  我们看到,首先需要将 「第一个元素」「第二个元素」 进行 「比较」,如果 前者 大于 后者,则进行 「交换」,然后再比较 「第二个元素」「第三个元素」 ,以此类推,直到 「最大的那个元素」 被移动到 「最后的位置」
  然后,进行第二轮「比较」,直到 「次大的那个元素」 被移动到 「倒数第二的位置」
  最后,经过一定轮次的「比较」「交换」之后,一定可以保证所有元素都是 「升序」 排列的。

二、题目描述

  给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

三、算法详解

整个算法的执行过程分以下几步:
  1) 定义是否还需要进行交换的标记变量swapped,当前需要将最大的元素放置到的位置last
  2) swapped置为fasle,迭代计算相邻元素,循环执行比较 a [ i ] a[i] a[i] a [ i + 1 ] a[i+1] a[i+1],如果产生 a [ i ] > a [ i + 1 ] a[i] \gt a[i+1] a[i]>a[i+1] 则交换两者的值,并且对swapped置为true
  3) 如果一次循环迭代完,swapped还是false则算法结束,否则继续执行 2)

四、源码剖析

#define Type int
void Swap(Type* a, Type* b) {
    Type tmp = *a;
    *a = *b;
    *b = tmp;
}

void BubbleSort(int n, Type *a) {            // (1)
    bool swapped;
    int last = n;
    do {
        swapped = false;                     // (2)
        for(int i = 0; i < last - 1; ++i) {  // (3)
            if(a[i] > a[i+1]) {              // (4)
                Swap(&a[i], &a[i+1]);        // (5)
                swapped = true;              // (6)
            }
        }
        --last;
    }while (swapped);
} 

void sortColors(int* nums, int numsSize){    // (7)
    BubbleSort(numsSize, nums);
}
  • ( 1 ) (1) (1) void BubbleSort(int n, int *a)为冒泡排序的实现,代表对a[]数组进行升序排序。
  • ( 2 ) (2) (2) swapped标记本轮迭代下来,是否有元素产生了交换。
  • ( 3 ) (3) (3) 每次冒泡的结果,会执行last的自减,所以待排序的元素会越来越少。
  • ( 4 ) (4) (4) 如果发现两个相邻元素产生逆序,则将它们进行交换。保证右边的元素一定不比左边的小。
  • ( 5 ) (5) (5) Swap实现了元素的交换,这里需要用&转换成地址作为传参。关于数据交换的更多内容,可以参考:《算法零基础100讲》(第16讲) 变量交换算法。
  • ( 6 ) (6) (6) 标记更新。一旦标记更新,则代表进行了交换,所以下次迭代必须继续。
  • ( 7 ) (7) (7) 题目要求实现的函数,我们直接调用冒泡排序的接口就能完成我们的功能。

五、推荐专栏

🌳《画解数据结构》🌳

冒泡排序

六、粉丝福利

序号题目链接难度
1颜色分类★☆☆☆☆
2寻找两个正序数组的中位数★☆☆☆☆
3至少是其他数字两倍的最大数★☆☆☆☆
👇🏻 关注公众号 观看 精彩学习视频👇🏻