文章目录
- 零、写在前面
- 一、概念定义
- 二、题目描述
- 三、算法详解
- 四、源码剖析
- 五、推荐专栏
- 六、粉丝福利
零、写在前面
这是《算法零基础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 | 至少是其他数字两倍的最大数 | ★☆☆☆☆ |
