【排序算法】图解冒泡排序(多图+解决两种无效比较问题)

写在前面：

本文主要介绍冒牌排序算法，通过图片一步步解释每一趟每一次的交换。并且，本文在给出冒泡排序基础版代码后，分析了基础版存在的两个问题，解决该问题可以避免出现不必要的比较。代码通过C#实现，并输出每一次交换的情况和比较次数，方便各位小伙伴比较算法的优缺点。

活动地址：CSDN21天学习挑战赛

本文关键字：经典算法、排序算法、交换排序、冒泡排序、图解、C#

文章目录

【排序算法】图解冒泡排序(多图+解决两种无效比较问题)
- - 一、排序算法分类
  - 二、算法效率
  - - 1. 时间复杂度
    - 2. 空间复杂度
  - 三、交换排序
  - - 1. 冒泡排序
    - 2. 快速排序
  - 六、算法实际
  - - 1. 图解算法原理
    - 2. 算法实现
    - 3. 优化版（解决两种无效比较的情况）
    - - a. 减少趟数
      - b. 减少每趟比较次数
    - 4.时间复杂度
    - 5.空间复杂度

一、排序算法分类

内部排序

指将需要处理的所有数据都加载到内部存储器（内存）中进行排序。
外部排序

数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序。
常见的分类方法

二、算法效率 1. 时间复杂度

度量一个程序（算法）执行时间的两种方法。

事后统计的方法

这种方法可行，但有两个问题：一是要想对设计的算法的运行性能进行评测，需要事件运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素。
事前估算的方法

通过分析某个算法的时间复杂度来判断哪个算法更优。
时间频度

一个算法花费的时间与算法中语句的执行次数成正比。一个算法中的语句执行次数称为语句频度或者时间频度。记为T(n)。

此处引用清华大学《数据结构》课程的一段话，一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。

2. 空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。

三、交换排序 1. 冒泡排序

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

2. 快速排序

快速排序Quick Sort是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

六、算法实际 1. 图解算法原理

冒泡排序的升序排列基本思想就是通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部。

下面通过一个动图来看一看冒泡排序到底是怎么样移动的。

那么，具体是如何移动的，我们以上面动图的数组[36, 26, 27, 2, 4, 19, 50, 48]为例。

假设我们有数组[36, 26, 27, 2, 4, 19, 50, 48]，要求按升序排列。

第1趟排序
- 第1次比较
  
  36和26比较，36较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续比较下面两个相邻的两个数大小关系。
- 第2次比较
  
  36和27比较，36较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第3轮比较。
- 第3次比较
  
  36和2比较，36较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第4轮比较。
- 第4次比较
  36和4比较，36较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第5轮比较。
- 第5次比较
  36和19比较，36较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第6轮比较。
- 第6次比较
  
  36和50比较，50较大，不交换位置。比较完毕之后，红色移动窗向后挪一位继续第7轮比较。
- 第7次比较
  
  50和48比较，50较大，交换位置。第一趟排序结束。
- 第一趟比较结果(比较次数是 8 - 1 - 0)
第2趟排序
- 第1次比较
  
  27和26比较，27较大，不交换位置。比较完毕之后，红色移动窗向后挪一位继续比较下面两个相邻的两个数大小关系。
- 第2次比较
  
  2和27比较，27较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第3轮比较。
- 第3次比较
  
  27和4比较，27较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第4轮比较。
- 第4次比较
  
  27和19比较，27较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第5轮比较。
- 第5次比较
  
  27和36比较，36较大，不交换位置。比较完毕之后，红色移动窗向后挪一位继续第6轮比较。
- 第6次比较
  
  36和48比较，48较大，不交换位置。第二趟排序结束。
- 第二趟比较结果(比较次数是 8 - 1 - 1)
第3趟排序
- 第1次比较
  
  2和26比较，26较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续比较下面两个相邻的两个数大小关系。
- 第2次比较
  
  26和4比较，26较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第3轮比较。
- 第3次比较
  
  19和26比较，26较大，交换位置。比较完毕之后，红色移动窗向后挪一位继续第4轮比较。
- 第4次比较
  
  26和27比较，27较大，不交换位置。比较完毕之后，红色移动窗向后挪一位继续第5轮比较。
- 第5次比较
  
  36和27比较，36较大，不交换位置。第三趟排序结束。
- 第三趟比较结果(比较次数是 8 - 1 - 2)
之后的第4、5、6趟排序同理。
第7趟排序 ( 7 = 8 - 1 )
- 第七趟比较结果(比较次数是 8 - 1 - 6)

从上述图解我们可以看出：

如果数组要求升序排列，那么每一趟排序就可以确定一个数，即第一趟能确定将末位上的数归位，第二趟能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。

进一步地，每一趟排序都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后红色窗体向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。这里需要强调的是，并不是每一趟排序都需要比较同样的次数。从图中我们可以看出，第1趟比较了7次，第2趟比较6次。以此类推，有 n 个数进行排序，第 i + 1 趟(循环中 i 是从 0 开始的)，我们只需要比较 n-1-i 次。

2. 算法实现

	/// 
	/// 冒泡排序静态类
	/// 
	public static class BubbleSort
    {
		// 将前面额冒泡排序算法，封装成一个方法
		public static void BubbleSortMethod(int[] arr)
		{
			// 冒泡排序 的时间复杂度 O(n^2)
			int temp = 0; // 临时变量
            int count = 0; // 计数比较次数
			for (int i = 0; i < arr.Length - 1; i++)
			{
				Console.WriteLine($"==============第{i + 1}趟排序==============");
				for (int j = 0; j < arr.Length - 1 - i; j++)
				{
					// 如果前面的数比后面的数大，则交换
					if (arr[j] > arr[j + 1])
					{
						temp = arr[j];
						arr[j] = arr[j + 1];
						arr[j + 1] = temp;
					}
					Console.WriteLine($"第{i + 1}趟第{j + 1}次交换后的数组");
					Console.WriteLine(string.Join(" ", arr));
				}
				Console.WriteLine($"第{i + 1}趟排序结果");
				Console.WriteLine(string.Join(" ",arr));
			}
            Console.WriteLine($"==============一共比较{count}次==============");
		}
	}

	class Program
    {
        static void Main(string[] args)
        {
            int[] intArray = new int[] { 36, 26, 27, 2, 4, 19, 50, 48 };

            //输出最大最小值
            //Console.WriteLine($"最大值{MaxMin.Max(intArray)}");
            //Console.WriteLine($"最小值{MaxMin.Min(intArray)}");

            //测试冒泡排序
            BubbleSort.BubbleSortMethod(intArray);

        }
    }

==============运行结果===============
==============第1趟排序==============
第1趟第1次交换后的数组
26 36 27 2 4 19 50 48
第1趟第2次交换后的数组
26 27 36 2 4 19 50 48
第1趟第3次交换后的数组
26 27 2 36 4 19 50 48
第1趟第4次交换后的数组
26 27 2 4 36 19 50 48
第1趟第5次交换后的数组
26 27 2 4 19 36 50 48
第1趟第6次交换后的数组
26 27 2 4 19 36 50 48
第1趟第7次交换后的数组
26 27 2 4 19 36 48 50
第1趟排序结果
26 27 2 4 19 36 48 50
==============第2趟排序==============
第2趟第1次交换后的数组
26 27 2 4 19 36 48 50
第2趟第2次交换后的数组
26 2 27 4 19 36 48 50
第2趟第3次交换后的数组
26 2 4 27 19 36 48 50
第2趟第4次交换后的数组
26 2 4 19 27 36 48 50
第2趟第5次交换后的数组
26 2 4 19 27 36 48 50
第2趟第6次交换后的数组
26 2 4 19 27 36 48 50
第2趟排序结果
26 2 4 19 27 36 48 50
==============第3趟排序==============
第3趟第1次交换后的数组
2 26 4 19 27 36 48 50
第3趟第2次交换后的数组
2 4 26 19 27 36 48 50
第3趟第3次交换后的数组
2 4 19 26 27 36 48 50
第3趟第4次交换后的数组
2 4 19 26 27 36 48 50
第3趟第5次交换后的数组
2 4 19 26 27 36 48 50
第3趟排序结果
2 4 19 26 27 36 48 50
==============第4趟排序==============
第4趟第1次交换后的数组
2 4 19 26 27 36 48 50
第4趟第2次交换后的数组
2 4 19 26 27 36 48 50
第4趟第3次交换后的数组
2 4 19 26 27 36 48 50
第4趟第4次交换后的数组
2 4 19 26 27 36 48 50
第4趟排序结果
2 4 19 26 27 36 48 50
==============第5趟排序==============
第5趟第1次交换后的数组
2 4 19 26 27 36 48 50
第5趟第2次交换后的数组
2 4 19 26 27 36 48 50
第5趟第3次交换后的数组
2 4 19 26 27 36 48 50
第5趟排序结果
2 4 19 26 27 36 48 50
==============第6趟排序==============
第6趟第1次交换后的数组
2 4 19 26 27 36 48 50
第6趟第2次交换后的数组
2 4 19 26 27 36 48 50
第6趟排序结果
2 4 19 26 27 36 48 50
==============第7趟排序==============
第7趟第1次交换后的数组
2 4 19 26 27 36 48 50
第7趟排序结果
2 4 19 26 27 36 48 50
==============一共比较28次==============

第一层循环是用来控制趟数，也就是 n 个数就要比较 n-1 趟；第二层是控制第 i +1 趟的比较次数， i+1 趟就是比较了 n-1-i 次。

我们通过运行结果可以看出，输出的结果与我们图解分析的内容是一致。

3. 优化版（解决两种无效比较的情况） a. 减少趟数

细心的朋友会发现，在上述例子中，我们在第4、5、6趟的排序都是多余，因为我们在第三趟的时候就已经得到了一个升序排列的数组，也就是说第4、5、6趟的排序没有进行交换。

因此在排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序。此时我们要在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较。

	/// 
	/// 冒泡排序静态类
	/// 
    public static class BubbleSort
    {
		// 将前面额冒泡排序算法，封装成一个方法
		public static void BubbleSortMethod(int[] arr)
		{
			// 冒泡排序 的时间复杂度 O(n^2)
			int temp = 0; // 临时变量
			int count = 0; // 计数比较次数
			bool flag = false; // 标识变量，表示是否进行过交换
			for (int i = 0; i < arr.Length - 1; i++)
			{
				Console.WriteLine($"==============第{i + 1}趟排序==============");
				for (int j = 0; j < arr.Length - 1 - i; j++)
				{
					// 如果前面的数比后面的数大，则交换
					if (arr[j] > arr[j + 1])
					{
						flag = true;
						temp = arr[j];
						arr[j] = arr[j + 1];
						arr[j + 1] = temp;
					}
					count++;
					Console.WriteLine($"第{i + 1}趟第{j + 1}次交换后的数组");
					Console.WriteLine(string.Join(" ", arr));
				}
				Console.WriteLine($"第{i + 1}趟排序结果");
				Console.WriteLine(string.Join(" ",arr));

				if (!flag)
				{ 
					break; // 在一趟排序中，一次交换都没有发生过
				}
				else
				{
					flag = false; // 重置flag, 进行下次判断
				}
			}
			Console.WriteLine($"==============一共比较{count}次==============");
		}
	}
==============运行结果===============
==============第1趟排序==============
第1趟第1次交换后的数组
26 36 27 2 4 19 50 48
第1趟第2次交换后的数组
26 27 36 2 4 19 50 48
第1趟第3次交换后的数组
26 27 2 36 4 19 50 48
第1趟第4次交换后的数组
26 27 2 4 36 19 50 48
第1趟第5次交换后的数组
26 27 2 4 19 36 50 48
第1趟第6次交换后的数组
26 27 2 4 19 36 50 48
第1趟第7次交换后的数组
26 27 2 4 19 36 48 50
第1趟排序结果
26 27 2 4 19 36 48 50
==============第2趟排序==============
第2趟第1次交换后的数组
26 27 2 4 19 36 48 50
第2趟第2次交换后的数组
26 2 27 4 19 36 48 50
第2趟第3次交换后的数组
26 2 4 27 19 36 48 50
第2趟第4次交换后的数组
26 2 4 19 27 36 48 50
第2趟第5次交换后的数组
26 2 4 19 27 36 48 50
第2趟第6次交换后的数组
26 2 4 19 27 36 48 50
第2趟排序结果
26 2 4 19 27 36 48 50
==============第3趟排序==============
第3趟第1次交换后的数组
2 26 4 19 27 36 48 50
第3趟第2次交换后的数组
2 4 26 19 27 36 48 50
第3趟第3次交换后的数组
2 4 19 26 27 36 48 50
第3趟第4次交换后的数组
2 4 19 26 27 36 48 50
第3趟第5次交换后的数组
2 4 19 26 27 36 48 50
第3趟排序结果
2 4 19 26 27 36 48 50
==============第4趟排序==============
第4趟第1次交换后的数组
2 4 19 26 27 36 48 50
第4趟第2次交换后的数组
2 4 19 26 27 36 48 50
第4趟第3次交换后的数组
2 4 19 26 27 36 48 50
第4趟第4次交换后的数组
2 4 19 26 27 36 48 50
第4趟排序结果
2 4 19 26 27 36 48 50
==============一共比较22次==============

我们通过运行结果可以看出，比较次数减少到了22次，并且只进行了4趟排序，避免了一部分不必要的比较。

b. 减少每趟比较次数

另外还有一种情况，如果数组中前半部分是无序的，后半部分的数值都大于前半部分并且是有序的，比如[19，26，2，4，27，36，48，50]这个数组，可以看出数组后半部分[27，36，48，50]的数值都大于前半部分并且是有序的，但是每一趟还是会去比较多次。

因此我们在每一轮排序的最后，记录一下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序了。

	/// 
	/// 冒泡排序静态类
	/// 
    public static class BubbleSort
    {
		// 将前面额冒泡排序算法，封装成一个方法
		public static void BubbleSortMethod(int[] arr)
		{
			// 冒泡排序 的时间复杂度 O(n^2)
			int temp = 0; // 临时变量
			int count = 0; // 计数比较次数
			bool flag = false; // 标识变量，表示是否进行过交换			   
			int lastChangeIndex = 0; //记录最后一次交换的位置					  
			int border = arr.Length - 1; //记录边界，每次比较只需要比到这里为止
			for (int i = 0; i < arr.Length - 1; i++)
			{
				Console.WriteLine($"==============第{i + 1}趟排序==============");
				for (int j = 0; j < border; j++)
				{
					// 如果前面的数比后面的数大，则交换
					if (arr[j] > arr[j + 1])
					{
						flag = true;
						temp = arr[j];
						arr[j] = arr[j + 1];
						arr[j + 1] = temp;
						lastChangeIndex = j;
					}
					count++;
					Console.WriteLine($"第{i + 1}趟第{j + 1}次交换后的数组");
					Console.WriteLine(string.Join(" ", arr));
				}
				Console.WriteLine($"第{i + 1}趟排序结果");
				Console.WriteLine(string.Join(" ",arr));
				border = lastChangeIndex;
				if (!flag)
				{ 
					break; // 在一趟排序中，一次交换都没有发生过
				}
				else
				{
					flag = false; // 重置flag, 进行下次判断
				}
			}
			Console.WriteLine($"==============一共比较{count}次==============");
		}
	}
==============运行结果===============
==============第1趟排序==============
第1趟第1次交换后的数组
26 36 27 2 4 19 50 48
第1趟第2次交换后的数组
26 27 36 2 4 19 50 48
第1趟第3次交换后的数组
26 27 2 36 4 19 50 48
第1趟第4次交换后的数组
26 27 2 4 36 19 50 48
第1趟第5次交换后的数组
26 27 2 4 19 36 50 48
第1趟第6次交换后的数组
26 27 2 4 19 36 50 48
第1趟第7次交换后的数组
26 27 2 4 19 36 48 50
第1趟排序结果
26 27 2 4 19 36 48 50
==============第2趟排序==============
第2趟第1次交换后的数组
26 27 2 4 19 36 48 50
第2趟第2次交换后的数组
26 2 27 4 19 36 48 50
第2趟第3次交换后的数组
26 2 4 27 19 36 48 50
第2趟第4次交换后的数组
26 2 4 19 27 36 48 50
第2趟第5次交换后的数组
26 2 4 19 27 36 48 50
第2趟第6次交换后的数组
26 2 4 19 27 36 48 50
第2趟排序结果
26 2 4 19 27 36 48 50
==============第3趟排序==============
第3趟第1次交换后的数组
2 26 4 19 27 36 48 50
第3趟第2次交换后的数组
2 4 26 19 27 36 48 50
第3趟第3次交换后的数组
2 4 19 26 27 36 48 50
第3趟排序结果
2 4 19 26 27 36 48 50
==============第4趟排序==============
第4趟第1次交换后的数组
2 4 19 26 27 36 48 50
第4趟第2次交换后的数组
2 4 19 26 27 36 48 50
第4趟排序结果
2 4 19 26 27 36 48 50
==============一共比较18次==============

我们通过运行结果可以看出，比较次数减少到了18次，并且只进行了4趟排序，第3趟仅进行3次比较，第4趟仅进行2次比较，避免了一部分不必要的比较。

4.时间复杂度

若数组是正序的，一趟即可完成排序。冒泡排序最好的时间复杂度为 O(n)。

从图中我们可以看出，8个数字需要7趟，第1趟比较了7次，第2趟比较6次。最后比较次数是7+6+ … + 1 = 28次，与上述代码输出一致。如果是 n 个数字，那么就是
( n − 1 ) + ( n − 2 ) + . . . + 2 + 1 = n ( n − 1 ) / 2 = n 2 / 2 − n / 2 (n-1)+(n-2)+...+2+1 = n(n-1)/2 = n^2/2 - n/2 (n−1)+(n−2)+...+2+1=n(n−1)/2=n2/2−n/2
根据复杂度的规则，去掉低阶项和常数系数，那复杂度就是O(n^2)。

5.空间复杂度

算法执行过程中，只需要一个临时变量temp来进行交换，所以空间复杂度是O(1)。

写在结尾：

文章中出现的任何错误请大家批评指出，一定及时修改。

希望写在这里的小伙伴能给个三连支持！

【排序算法】图解冒泡排序(多图+解决两种无效比较问题)

Java相关栏目本月热门文章