数据结构与算法系列之一：八大排序之冒泡排序

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 1,782 | 阅读时长 ≈ 7

[toc]

冒泡排序

前言

  建议先看排序综述，传送门：数据结构与算法系列之一：八大排序综述。

简介

  冒泡排序（英语：Bubble Sort，台湾另外一种译名为：泡沫排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  冒泡排序对 ${\displaystyle n}$ 个项目需要${\displaystyle O(n)}$ )的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

步骤

冒泡排序算法的运作如下：

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

演示

  wikipedia的大数据规模演示：


bubblesort from wikipedia

  wordzzzz的小数据规模演示：


bubblesort from wordzzzz

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 
 * 标准冒泡排序：嵌套循环比大小。
 */ 

template <typename T>
void BubbleSort(T *array, const int length) {
	if (array == NULL)
		throw invalid_argument("Array must not be empty");
	if (length <= 0)
		return;

	for (int i = 0; i < length - 1; ++i){				//外循环，每次循环确定一个最大值
		for (int j = 0; j < length - 1 - i; ++j){		//内循环，用于交换数据，遍历次数递减
			if (array[j] > array[j + 1]){				//如果当前数据比后面的数据大，则交换
				T tmp = array[j + 1];
				array[j + 1] = array[j];
				array[j] = tmp;
			}
		}
	}
}

算法复杂度

  • 数据结构 数组
  • 最坏时间复杂度 ${\displaystyle O(n^{2})}$
  • 最优时间复杂度 ${\displaystyle O(n)}$
  • 平均时间复杂度 ${\displaystyle O(n^{2})}$
  • 空间复杂度 总共 ${\displaystyle O(n)}$，需要辅助空间 ${\displaystyle O(1)}$

分析

  冒泡排序是与插入排序拥有相等的运行时间，但是两种算法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要 ${\displaystyle O(n^{2})}$次交换，而插入排序只要最多 ${\displaystyle O(n)}$ 交换。冒泡排序的实现（类似上面）通常会对已经排序好的数列拙劣地运行（ ${\displaystyle O(n^{2})}$ ），而插入排序在这个例子只需要 ${\displaystyle O(n)}$ 个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。

  在面试中，一般都会涉及到算法的优化，重点考察的其实还是你对现有算法的理解，分析现有算法的缺点，就能找到优化的思路。

优化1：冒泡排序如果能在内部循环第一次运行时，使用一个旗标来表示有无需要交换的可能，也可以把最优情况下的复杂度降低到 ${\displaystyle O(n)}$ 。在这个情况，已经排序好的数列就无交换的需要。
优化2：可以记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。
优化3：若在每次走访数列时，把走访顺序反过来，也可以稍微地改进效率。有时候称为鸡尾酒排序，因为算法会从数列的一端到另一端之间穿梭往返。

优化代码如下：

优化1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 冒泡排序优化1：如果某次内循环没有改变任何数据，则结束。
 */

template <typename T> 
void BubbleSort1(T *array, const int length) { 
	if (array == NULL)
		throw invalid_argument("Array must not be empty"); 
	if (length <= 0) 
		return; 
	bool flag = false;									//设置标志位，用来判断内循环是否有数据交换
	for (int i = 0; i < length - 1; ++i){				//外循环，每次循环确定一个最大值
		flag = false;									//外循环第一步需要重置标志位
		for (int j = 0; j < length - 1 - i; ++j){		//内循环，用于交换数据，遍历次数递减
			if (array[j] > array[j + 1]){				//如果当前数据比后面的数据大，则交换
				T tmp = array[j + 1];
				array[j + 1] = array[j];
				array[j] = tmp;
				flag = true;							//如果有交换，则标志位置1
			}
		}
		if (!flag) return;								//如果本次循环没有数据交换，则结束排序
	} 
}

优化2：

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：在优化1的基础上，记录上次排序结束位置，减少排序次数。
*/

template <typename T>
void BubbleSort2(T *array, const int length) {
	if (array == NULL)
		throw invalid_argument("Array must not be empty");
	if (length <= 0)
		return;
	int k = length;
	int flag = k;										//设置标志位，用来判断内循环是否有数据交换
	for (int i = 0; i < length - 1; ++i){				//外循环，每次循环确定一个最大值
		k = flag;
		flag = 0;										//外循环第一步需要重置标志位
		for (int j = 0; j < k - 1; ++j){				//内循环，用于交换数据，遍历次数递减
			if (array[j] > array[j + 1]){				//如果当前数据比后面的数据大，则交换
				T tmp = array[j + 1];
				array[j + 1] = array[j];
				array[j] = tmp;
				flag = j + 1;							//如果有交换，更新交换位置的记录
			}
		}
		if (!flag) return;								//如果本次循环没有数据交换，则结束排序
	}
}

优化3：

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
27
28
29
30
31
32
33
34
35
36
37
38
/*
 *冒泡排序优化3：鸡尾酒排序，一个外循环内跑两个内循环。
 */

template <typename T>
void BubbleSort3(T *array, const int length) {
	if (array == NULL)
		throw invalid_argument("Array must not be empty");
	if (length <= 0)
		return;
	int low = 0;
	int high = length - 1;

	while (high > low)
	{
		for (int i = low; i < high; ++i)				//正向冒泡，确定最大值  
		{
			if (array[i] > array[i + 1])
			{
				T temp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = temp;
			}
		}
		--high;

		for (int j = high; j > low; --j)				//反向冒泡，确定最小值  
		{
			if (array[j] < array[j - 1])
			{
				T temp = array[j];
				array[j] = array[j - 1];
				array[j - 1] = temp;
			}
		}
		++low;
	}
}

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz

0%