一、什么是冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单且最基础的排序算法，是新手入门学习排序算法的必经之路。

冒泡排序的思路非常简单，就是不断选出数组中的最大值或最小值，每选出一个数，参与选举数组长度减一。

从下图中可以形象的看到，越大的数字代表越大的泡泡，从而最先往上浮，泡泡最终根据大小先后浮出水面。

二、冒泡排序的实现

1 基本实现思路

冒泡排序有几种简单的实现方式，我在这里将以从小到大排列数组为例展示冒泡算法。

假定有一数组

5 , 2 , 4 , 6 , 1 , 3 {5,2,4,6,1,3} 5,2,4,6,1,3

我们要如何将其进行从小到大排列呢？

1. 首先，我们找到这个数组中的最大值，也就是6，让它与最后的数字3交换，得到：

   5 , 2 , 4 , 3 , 1 , 6 {5,2,4,3,1,6} 5,2,4,3,1,6​​

2. 此时作为最大数的6已经就位，我们关注的数组范围减少一位，也就是说我们将不再关注6。

   5 , 2 , 4 , 3 , 1   { 6 } {5,2,4,3,1}\ \{6\} 5,2,4,3,1 {6}​​​

3. 我们从剩下的数字中寻找最大的数，也就是5，将其和倒数第二位的数进行交换，得到：
   1 , 2 , 4 , 3   { 5 ， 6 } {1,2,4,3}\ \{5，6\} 1,2,4,3 {5，6}​

4. 接下来则按照这个规则继续，最后得到
   1 , 2 , 3 , 4 , 5 , 6 {1,2,3,4,5,6} 1,2,3,4,5,6​

是不是非常简单！Ψ(￣∀￣)Ψ

2 求最大值

在上述描述中我隐藏了提取最大值的方式，这里有两种方式来获取最大值。

1. 在最基础的冒泡排序算法里，我们一般通过不断对比相邻数字，从而原址筛选出最大值，如针对

   { 5 , 2 } , 4 , 6 , 1 , 3 \{5,2\},4,6,1,3 {5,2},4,6,1,3​​

   首先对比5和2，5大于2，交换两者，得到

   2 , { 5 , 4 } , 6 , 1 , 3 2,\{5,4\},6,1,3 2,{5,4},6,1,3​​

   继续对比5和4，5大于4，交换两者，得到

   2 , 4 , { 5 , 6 } , 1 , 3 {2,4,\{5,6\},1,3} 2,4,{5,6},1,3​

   继续对比5和6，5小于6，保持不变，得到

   2 , 4 , 5 , { 6 , 1 } , 3 {2,4,5,\{6,1\},3} 2,4,5,{6,1},3

   对比6和1，1小于6，交换两者，得到

   2 , 4 , 5 , 1 , { 6 , 3 } {2,4,5,1,\{6,3\}} 2,4,5,1,{6,3}

   最后对比6和3，3小于6，交换两者，得到

   2 , 4 , 5 , 1 , 3 , { 6 } 2,4,5,1,3,\{6\} 2,4,5,1,3,{6}​

   这种方法虽然找出了最大值，但是一般来说需要多次交换数组中的元素，造成了不必要的时间浪费，毕竟我们的目的只是为了获得最大值，因此，有了第二种方法。

2. 在第二种方法中需要一个额外的变量，我们把它命名为 max。

   首先我们使其记录数组中首个数字的下标，在一般编程语言中以0开始，就让其等于0。

   随后，将数组中数字与max所记录下标表示数字进行对比，若数字大于max所记录下标表示数字，则让max记录新的数字的下标。

   最后，交换max记录下标数字与最后的数字。

   5 , 2 , 4 , 6 , 1 , 3 {5,2,4,6,1,3} 5,2,4,6,1,3

   在这个数组中的第一轮，我们让max记录0也就是代表5；

   拿5分别和 2 4 6 1 3进行比较，前面2 4均小于5，因此max保持不变，随后5小于6，因此max变为3，也就是代表6；

   随后1 3 均小于6，max保持不变，因此得到最大的数的下标为3，代表数字6；

   最后交换第3位数字与最后1位数字（第5位），获得 2 , 4 , 5 , 1 , 3 , { 6 } 2,4,5,1,3,\{6\} 2,4,5,1,3,{6}​​。​

   这种方法避免了过多的交换，节省了一点时间。

3 伪代码实现

下面我们通过伪代码进行实现

第一种方式进行最大值提取的代码

get arr[] and arr.length //我们获取一个数组 arr ,并且得到它的长度 arr.length

// 第一层循环，表示参与寻找最大值的数组，开始为整个数组（最后元素的下标为arrlength-1），最后只剩一个元素时不需要寻找最大值
for i = (arrlength-1) to 1 
	//第二层循环，不断对比相邻数字（对比j与j-1）
	for j = 1 to i-1 
		if arr[j]>arr[j-1]
			exchange arr[j-1] and arr[j]// 交换最后j和j-1
		endif
	endfor
endfor

第二种方式进行最大值提取的代码

get arr[] and arr.length //我们获取一个数组 arr ,并且得到它的长度 arr.length

// 第一层循环，表示参与寻找最大值的数组，开始为整个数组（最后元素的下标为arrlength-1），最后只剩一个元素时不需要寻找最大值
for i = (arrlength-1) to 1 
	max = i // max记录首个元素下标
	//第二层循环，对比max代表的数字与参与寻找最大值的数字,因为max代表了下标为0的数字，所以从1开始对比
	for j = i-1 to 1 
		if arr[j]>arr[max]
			max = j;
		endif
	endfor
	exchange arr[max] and arr[i] // 交换最后一个数字和最大值
endfor

是不是非常简洁和简单！这里只给出了伪代码的原因是，伪代码的可读性高于真实的代码，我也会给出一份c++实现的代码，关注公众号 愿人人如龙 回复冒泡排序即可免费领取（代码非常简陋，仅供学习使用）。

到了这里，冒泡排序就完了吗？不不不，我们再来看一种特殊情况

1 , 2 , 3 , 4 , 5 , 6 {1,2,3,4,5,6} 1,2,3,4,5,6

1 , 2 , 3 , 4 , 6 , 5 {1,2,3,4,6,5} 1,2,3,4,6,5​

1 , 2 , 4 , 3 , 6 , 5 {1,2,4,3,6,5} 1,2,4,3,6,5

对，就是完全排完序或前面部分排序时。

当我们把后面部分排序完毕后，前面的排序无需继续，因为那只是白白浪费时间，那问题是如何去检测这种情况呢？

这对于第一种方式进行最大值提取来说非常简单，只需要增加一条判断。

get arr[] and arr.length 

for i = (arrlength-1) to 1 
	flag = true // 增加一个判断的标志	《------新增
	for j = 1 to i-1 
		if arr[j]>arr[j-1]
			exchange arr[j-1] and arr[j]
			flag = false // 如果发生了数字的交换则把flag置为false	《------新增
		endif
	endfor
	// 如果一次交换都没发生，代表前面部分已经处于排好序的状态	《------新增
	if flag
		break;
	endif	
endfor

对于这种方式来说，检测这种情况非常简单，但对于第二种来说需要额外牺牲一些时间来到达目的，这是否值得也是不确定的，这里就不展开了，我们要做的是熟悉算法的思路与特点，最后判断使用何种算法，算法在大部分时间不分好和坏，只分合不合适。

quiz：这里我们没有讨论如果数组中有数字是相等的会发生什么，会影响我们的排序吗？（答案是不会）对于不太清楚的童鞋可以尝试一下并思考一下，为什么？

三、冒泡排序算法的分析

关于算法的分析，我们主要讨论时间与空间复杂度。

1 空间复杂度

一般来说，空间复杂度不太重要，我们只需要了解其大致需要哪些空间就行。

空间复杂度就是在排序过程中临时变量所占的内存空间，在这个过程中交换数字需要临时变量，max、flag 均算临时变量，他们相比于数组的输入规模 n n n​​ 来说是常量，不随 n n n 的变化而变化。

在空间复杂度的分析中，有一个问题，可以重复利用的变量空间，需要对其进行空间复杂度计算吗，例如对于交换数字需要临时变量，每一次大循环，需要有一个临时变量，但是这个临时变量可以重复利用，如果考虑 n n n​​ 次循环，每次循环都进行数字交换，不考虑重复利用则需要 Θ ( n ) \Theta(n) Θ(n)​​ 个空间，考虑重复利用则只需要 Θ ( 1 ) \Theta(1) Θ(1)​​​​​​ ，一般来说，我们对于不同循环的还是重复计算，主要是虽然在实际中，诸如单个变量我们可以确保重复使用，但并不是所有情况，临时变量都可以确保重复使用。

因此，上述几种不同的冒泡排序实现在不同情况下，有不同的空间复杂度，但是详尽的去分析意义不大。

但是，对于冒泡排序，我们只需要知道其只需要常数个临时空间就够了，并且这些空间可以重复使用。

2 时间复杂度

之前我们提到时间复杂度主要由算法时间函数的增长量级决定，在这里我们假定数据计算、变量定义赋值、交换、判断的时间均为1，在更精细的分析中应设定其抽象的运行时间 a i a_i ai​​ 来定义不同的操作。

因此，对于冒泡排序，我们主要是分析其双层循环部分。

第一个版本

对于第一个版本（按上面伪代码顺序），对于 n n n​ 个数

第一层循环第一次循环内部需要

对比相邻数字 n − 1 n-1 n−1​ 次，交换元素 a 1 ( n − 1 ) a_1(n-1) a1​(n−1)，其中 0 ≤ a 1 ≤ 1 0\le a_1\le 1 0≤a1​≤1

第一层循环第而次循环需要

对比相邻数字 n − 2 n-2 n−2​​​ 次，交换元素 a 2 ( n − 2 ) a_2(n-2) a2​(n−2)​​​，其中 0 ≤ a 2 ≤ 1 0\le a_2\le 1 0≤a2​≤1​​​

…

最后，考虑最好的情况，即 a 1 . . . a n − 1 a_1...a_{n-1} a1​...an−1​​​ 均为0，当数组按顺序排好时成立：

时间为： ( n − 1 ) + ( n − 2 ) + . . . + 1 (n-1)+(n-2)+...+1 (n−1)+(n−2)+...+1

根据等差数列求和，得到 n ( n − 1 ) 2 \displaystyle\frac{n(n-1)}{2} 2n(n−1)​​

考虑最差情况，即 a 1 . . . a n − 1 a_1...a_{n-1} a1​...an−1​ 均为1，当数组按逆序排好时成立：

那时间为 n ( n − 1 ) n(n-1) n(n−1) ​

最好最差的时间复杂度均为 Θ ( n 2 ) \Theta(n^2) Θ(n2) ，那根据夹逼准则，最好<平均情况<最坏，因此也是 Θ ( n 2 ) \Theta(n^2) Θ(n2) ；

第二个版本

第一层循环第一次循环内部需要：

定义max需要1次，对比数字 n − 1 n-1 n−1​​​ 次，交换数字（实际程序中需要3次）1次，共 n + 1 n+1 n+1 次。

后续每一层循环减1，最后总时间构成一个等差数列，时间复杂度为 Θ ( n 2 ) \Theta(n^2) Θ(n2)​​​​ ，这是最差情况。

最好情况在于不需要交换数字，所以 a n 2 − n an^2-n an2−n​ , 时间复杂度同样为 Θ ( n 2 ) \Theta(n^2) Θ(n2)​。

同理，根据夹逼准则，最好<平均情况<最坏，因此也是 Θ ( n 2 ) \Theta(n^2) Θ(n2) ；

第三个版本

最坏情况下相比第一个版本多了 Θ ( n ) \Theta(n) Θ(n) 次关于flag的操作，因此最差情况时间复杂度为 Θ ( n 2 ) \Theta(n^2) Θ(n2)​ 。

最好情况为已经按顺序排好，需要 n − 1 n-1 n−1​ 次对比，加1次flag定义和1次flag赋值，因此最好情况时间复杂度为 Θ ( n ) \Theta(n) Θ(n)​ 。

在这里最差的情况和最好的情况不一致，因此，不能像上面两个版本一样直接得到平均情况时间复杂度，需要一点概率论的知识，分析过程比较复杂，这里就不对其进行分析，其平均运行时间也同样为 Θ ( n 2 ) \Theta(n^2) Θ(n2)。​

四、结语

排序算法作为一个经典的算法，虽然其不是一个非常好的算法，但是其中蕴含的思想非常适合初学者，是每个学习算法的人必学的排序算法，下一节将讲解归并排序算法。