极简理解算法理解 --冒泡排序_冒泡排序是从左到右还是从右到左

题外话

本篇讲解主要是面对冒泡排序的初学者，讲解的时候比较细腻，可能会有点冗长，最后会给出冒泡的关键记忆点，以便在编程时快速实现。

冒泡排序的思想

冒泡排序就是通过每次相邻的两位数进行比较，把较大的数往右边移动一位，每次都比较相邻的两位，直到该行最大的数移动到最右边。用同样的方式继续对该行中第二大，第三大，第 n 大的数进行类似的操作，最终得到由小到大的排序。（由大到小的排序方式与此类似，下面的讲解是按照由小到大排序操作的）。

实际分析

冒泡排序的定义看起来是非常抽象和令人不解的，下面通过一个实际的例子来展示整个过程。

现在我们有一行需要排序的数，“5，14，3，1，9”。

首先我们观察一共现在有 5 个数需要排序，按照冒泡的定义，我只需要排出最右边 4 个的位置，那第一个位置的数字自然而然就落实了。所以一共需要进行 4 次大的行排序。（我在这里称之为外循环）

其次，我们再观察，还有一个内循环，是指每一次外循环时，内部要进行的循环，我们将在接下来的实际排序中讲到。

至于为什么我用外循环，内循环来表示会在代码实例部分解释。

开始排序（整行数字从左往右，实现从小到大排序）

Note：
1.图中的 1.1，2.2 代表的是（第1次外循环第1次内循环，第2次外循环第2次内循环 … 总之，第一个是外循环的次数，第二个是内循环的次数）。
2.绿色圈表示该轮进行比较的两个数字，图中显示的是已经比较完后的结果。所以跟着看的读者可以自己动笔，跟着算。
3.红圈表示位置已经完全确定，不会再改变的数字（已经排好序的数字）

第一次外循环
1.1 从左往右开始，第一个数字 5 和第二个数字 14 进行比较，两者的顺序是符合要求的，所以不动。所以第一次外循环第一次内循环的排序结果如 1.1 所示。

1.2 这个时候比较 14 和 3（注意，是比较接下来相邻的两个数字，而不是又拿 5 去比较噢），我们发现 14 > 3 ，应该调换顺序，排在 3 后面。所以第一次外循环第二次内循环的排序结果如 1.2 所示。

1.3 接下来比较 14 和 1，14 > 1 应该排在 1 的后面，于是第一次外循环第三次内循环的排序结果如 1.3 所示。

1.4 现在自己动手看看在第一次外循环第三次内循环的排序结果，再比较和图中的排序结果是否一样。

这样第一次外循环再经历了 4 次内循环后结束，而 14 这个改行最大的数字像冒泡泡一样，漂到了最右边。

第二次外循环
在此之前想想，改行最大的数 14 已经被漂到了最右边，即位置已经确定了，不管后面再怎么排序都不会改变 14 的位置，换言之，在接下来的排序中，我们将不会在理会 14 ，可以看到 14 被红圈框住，表示位置已经固定了，你甚至可以在接下来的排序中完全忽视它。

2.1 接下来我们依然从改行的最左边开始比较，5 > 3 ，所以 5 需要和 3 调换顺序，于是第二次外循环第一次内循环的排序结果如 2.1 所示。

2.2 同理 5 和 1也需要调换顺序，第二次外循环第二次内循环的排序结果如 2.2 所示。

2.3 5 和 9 位置符合要求的顺序，所以不变，第二次外循环第三次内循环的排序结果如 2.2 所示。

至此，第二次外循环排序结束，正如我们说的那样，14 已经被固定住了，所以不需要参与排序，你完全可以忽视它。

我们看到本轮排序，内部只进行了 3 次（第一轮是 4 次），大胆猜想一下，下一轮的内排序的次数，然后自行对第三次外循环进行 n 次内循环的排序，然后对比上图中的结果。

第四次外循环
第三轮外循环的结果由读者自行完成然后比对上图的结果，不知道你算对没有。

接下来是第 4 次外循环。

可以看到 5 个数字此时右边的 3 个我们已经确定了（完全不用理会了），还剩左边的两个数字，1 和 3 ，它们符合要求的顺序，不用调换。

然后没有数字可以比较了，3 的位置被固定。

此时我们已经不需要对 1 再进行排序了，因为 1 的位置无论怎样都不会改变了.

所以最终的结果 “1，3，5，9，14”.

代码实例

C 语言版

#include <stdio.h>
main()
{ 
	int a[5] = {5,14,3,1,9};
	int temp;
	
	for(int i=0;i<5-1;i++)
	{
		for(int j=0;j<5-1-i;j++)
		{
			if(a[j]>a[j+1])
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}
	
	// 输出
	for(int i=0;i<5;i++)
	{
		printf("%d ",a[i]);
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

C++ 版

#include <iostream>
#include <vector>

using namespace std;

int quickSort()
{
    vector<int> vec = { 5,14,3,1,9 };
    int temp = 0;

    for (int i = 0; i < vec.size() - 1; ++i) {
        for (int j = 0; j < vec.size() - 1 - i; ++j) {
            if (vec[j] > vec[j + 1]) {
                temp = vec[j];
                vec[j] = vec[j + 1];
                vec[j + 1] = temp;
            }
        }
    }

    for (auto& v : vec) {
        cout << v << " ";
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

可以看到，冒泡算法的实现需要两个循环，这就是我所说的外循环和内循环，当然我只是为了讲解方便，熟练使用的时候，完全可以忽略这种说法。

关键点

那么虽然冒泡算法不难理解，但是在用代码实现的时候很多人的困难点就是搞不清楚两次循环的表达式2（本例中的 i<5-1 和 j<5-1-i）的情况。

我们观察，一共 5 个数字，外部循环了 4 次，内部循环是 4次，3次，2次，1次。推广归纳可以得到，一共有 n 个数字，外部循环等于 n-1 次，内部循环等于 n-1-i 次。

在代码里，因为我们是从 i=0 开始的，所以循环次数不取等于，而是小于。有时候你会看到表达式2出现等于符号，那么多半是 i=1 开始取值，建议还是用 i=0，更符合计算机思维。

所以如果非要死记硬背也很简单，只要记住 i=0，i<n-1 和 j<n-1-i这三个关键点，往代码里面一套就完成了

还有一点很重要，就是很多人纠结已经符合顺序的两个数字是否进行比较或者是否纳入循环次数中，比如 3 和 5 已经符合顺序了，还需要进行所谓的排序吗。答案是肯定的，因为计算机很笨的，人一眼看出，啊，这个已经符合顺序了，但是计算机只有在进行比较之后才知道，所以即使顺序符合条件也需要纳入循环次数。

完毕！