01
故事起源
幼儿园放学，小朋友们集合，需要先从低到高排队，应该怎么排呢？
文章插图
02
开始行动
小K身高180，是班里最高的，自然得往后排啦 。小K先和身后的小B比较，然后和小B交换 。
文章插图
小K接着和身后的小D比较，然后和小D交换 。
文章插图
经过和4个小朋友交换位置，小K终于找到自己的位置啦 。
文章插图
上面的过程其实就是冒泡排序的核心思想了 。
03
冒泡排序
为描述方便，用下面的数组模拟小朋友的交换过程 。
文章插图
核心思想(升序)：
从首位置开始，依次比较前后两个数，如果前面的数比后面的数大，就交换两个数 。这样第1轮结束后，最大的数就会移动到最后的位置 。对剩余元素重复执行N-1次，整个数组有序 。因为像空气上浮到水面，最大的元素会慢慢浮到最后，所以冒泡因此得名 。
3.1
第1轮
执行完成后，最大的元素归位 。
文章插图
3.2
第2轮
第2轮接着对前面剩余的N-1个元素重复上面步骤，第2大的元素归位 。
文章插图
3.3
第3轮
第3轮对前面剩余的N-2个元素重复上面步骤，第3大的元素归位 。
文章插图
总共执行N-1次操作，所有元素归位 。
3.4
代码实现
for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); } }} 04
问题及优化
4.1
迭代轮次优化
如果原数组为如下情况，那么在执行完第1轮后，整个数组已经有序，后面的轮次没必要执行，可以针对这种情况做一次优化改进 。
改进点1：
如果某一轮没有发生过交换，说明数组已经有序，那么以后也不会发生交换，此时可以终止迭代 。
文章插图
代码实现
for (int i = 0; i < n - 1; ++i) { // flag标记是否有交换 bool flag = true; for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = false; } } if (flag) { break; }} 4.2
扫描范围优化
如果为以下情况，我们会发现最后的6和8所处的位置和最终排序完成的位置一样，说明过程中他们的位置不会发生变化 。
文章插图
上一轮最后交换的位置，在下一轮时，此位置后面的数也不会再发生交换 。
文章插图
改进点2：
记录每一次最后发生交换的位置，下一轮只需要扫描到此位置的前一个即可 。
代码实现
// 记录最后交换的位置int position = 0;int len = n - 1;for (int i = 0; i < n - 1; ++i) { // flag标记是否有交换 bool flag = true; for (int j = 0; j < len; ++j) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = false; position = j; } } len = position; if (flag) { break; }}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 眼妆|藏在屈臣氏“角落”的5款洗发水，导购不推荐都留自用，孕期可用
- 常见菩提子,常见的菩提子的种类都有哪些
- 大袋鼠都吃哪些食物？
- 都江堰坐落在哪个平原？
- 早饭只喝酸奶好吗？
- 防腐剂食物有哪些？
- 游泳后注意什么呢？
- 土豆不能与什么同吃会怎样
- 经常吃蔬菜水果沙拉减肥吗
- 榴莲和酸奶能在一起吃吗
![[快科技]小米10青春版邀请函图赏：哆啦A梦迷你抓娃娃机](http://ttbs.guangsuss.com/image/3edcbb553cbab8a02c1d1c782772809f)
