介绍及原理

冒泡排序法具有稳定性，且应用场景广泛且普遍。其主要原理是通过对一个数组进行两次循环迭代，最外层的循环迭代决定了其检测的次数，里层的循环迭代用于判断两个相邻的数的大小，如果前一个数大于它的后一个数，则两数交换位置，依次循环，直到排序完毕。

时间复杂度： O(n^2)

冒泡排序法

示例

注：示例采用C语言，C++同样适用

代码如下：

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
#include <stdio.h>

void bubble_sort(int arr[], int len) {
	int temp; //临时存储数据
	for (int i = 0; i < len - 1; i++) {
		for (int j = 0; j < len - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) { //如果前一项大于后一项，执行交换操作
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

void main() {
	int arr[] = { 42,53,63,13,4,35,6,2,0,14,56,22,85,76,35,24,78,98,77,53,23,16,76 };
	int len = sizeof(arr) / sizeof(*arr); //获取数组长度
	printf("排序前：");
	for (int i = 0; i < len; i++) { //输出排序前的数组
		printf("%d ", arr[i]);
	}
	bubble_sort(arr, len); //调用排序函数
	//迭代输出排序好的数据
	printf("\n排序后：");
	for (int i = 0; i < len; i++) { //输出排序后的数组
		printf("%d ", arr[i]);
	}
}

以上示例输出如下：

1
2
排序前：42 53 63 13 4 35 6 2 0 14 56 22 85 76 35 24 78 98 77 53 23 16 76
排序后：0 2 4 6 13 14 16 22 23 24 35 35 42 53 53 56 63 76 76 77 78 85 98

详细讲解

void bubble_sort(int arr[], int len){}

第一个参数用于传入需要排序的目标数组。

第二个参数用于传入数组的长度，用于循环迭代。

for(int i = 0; i < len - 1; i++){}

第一层for循环，用于决定检测次数。

for(int j = 0; j < len - 1 - i; j++){}

第二层for循环，可以根据条件交换两个数的位置

if (arr[j] > arr[j + 1])

第二层for循环下，循环检测前一个数是否大于它的后一个数，如果大于，则触发交换操作

1
2
3
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

先将前一个数arr[j]临时存入temp中，再将后一个数arr[j+1]赋值给前一个数arr[j]，然后再将temp变量中的数存入arr[j+1]中，达成了变相交换数的操作，可以把temp想象成中介，arr[j]和arr[j+1]是交换方，需要通过中介才能交换所需要的材料。这样能更好理解

依此循环迭代交换，直到最外层循环迭代完毕，所有数将排序完成。