前言：什么是冒泡排序？

📝冒泡排序(Bubble Sort)，是一种计算机科学领域的较简单的排序算法

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”

引用于 百度百科-冒泡排序 📖

算法思想：

冒泡排序，最核心的地方在于将数组内的相邻元素去比较大小，如果前一个元素大于后一个元素，那么就将他俩相互交换，然后在和后面的所有元素依次比较，直到将数组内的所有元素排序好😮

下面使用动图来解释一下这个排序的具体过程📟

算法实现：

当每执行一趟后就得到了数组中的一个最大值，这个值会在与相邻元素比较下，不断的向后移，直到移动到最后面，此时就确定了一个相对大的数值😋

但是这个远远不够，我们的目标是将数组内的所有元素依次从小到大排列🤔

所以我们要定义两个循环，一个用于去找数组内的相对最大值，而另一个是用于外层循环，来确定要循环的次数🤨

//java代码
for (int i = 1 ;i < Arr.length ;i++) {		 //外层循环
	for(int j = 0 ;j < Arr.length - i ;j++) {//内层循环
        //判断和交换...
	}
}

外层循环作用是帮助内层循环去依次比较相邻元素，如果没有外层循环程序就变成了找数组的最大值😅

此格式基本是固定格式，即外层循环和内层循环的终值为数组元素的个数，但上述代码的内层循环却做了 - i 操作🤔

这里之所以使用Arr.length - i是因为每次找到的最大值都会被交换到数组末尾，所以数组末尾已经是一个定值，也就是我们这一遍找到的相对最大值，所以使用 - i 的方式可以减少计算量，提高执行速度😀

接下来是判断相邻元素是否大于前面的元素

//java代码
if (Arr[j] > Arr[j + 1]) {//判断相邻元素是否大于前面的元素
	//交换数据
}

即内层循环的变量 j 假如 j 是 2 那么相邻元素是 3 即 Arr[2] 的相邻元素是 Arr[3] 写成条件就是 Arr[j] > Arr[j + 1] 其中的 j 为内层循环的变量😁

到这里就差交换两个元素就可以完成算法的编写了，接下来会介绍四种交换方式

1.中间变量法

int A = 10;		//定义要交换的两个变量
int B = 20;
/*-----------------------*/
int Temp = 0;	//定义临时变量
Temp = A;		//临时存放变量A
A = B;			//先将B的数给A
B = Temp;		//Temp存放的是交换前的A
//完成交换

优点：简单易懂✨

2.数学运算法

int A = 10;		//定义要交换的两个变量
int B = 20;
/*-----------------------*/
A = A + B;		//将AB叠加-> 10 + 20 = 30
B = A - B;		//A - B  -> 30 - 20 = 10
A = A - B;		//A - B  -> 30 - 10 = 20
//完成交换

优点：节省内存✨

3.异或法

int A = 10;		//定义要交换的两个变量
int B = 20;
/*-----------------------*/
A = A ^ B;		//A ^ B = 30
B = A ^ B;		//A ^ B = 10
A = A ^ B;		//A ^ B = 20
//完成交换

这里解释一下10的二进制是 0000 1010 ，20的二进制是 0001 0100

10 ^ 20 = 0000 1010 ^ 0001 1110 -> 0001 1110 = 30

30 ^ 20 = 0001 1110 ^ 0001 0100 -> 0000 1010 = 10

30 ^ 10 = 0001 1110 ^ 0000 1010 -> 0001 0100 = 20

注：此方法只适用于整数📌

4.特殊法

int A = 10;		//定义要交换的两个变量
int B = 20;
/*-----------------------*/
B = A + B - (A = B);
//交换完成

我们对B = A + B - (A = B) 进行编译后，在反编译 可以看到如下代码

int X = A + B
B = A
A = X - A

为了简洁明了我们使用第一种方法来作为我们冒泡排序的交换方式🖋(中间变量法)

int a = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = a;

交换完成后，内层循环会去判断下一个相邻元素，这样依此类推...✏

完整代码：

以Java为例，奉上完整代码🎉

//Java代码
package Project;
public class Universal {
    public static void main(String[] args) {
		int[] arr = {4,2,8,0,5,7,1,3,9,10};							
		for (int i = 1 ;i < arr.length ;i++) {
			for(int j = 0 ;j < arr.length - i ;j++) {
				if (arr[j] > arr[j + 1]) {
					int a = arr[j];	
					arr[j] = arr[j + 1];
					arr[j + 1] = a;
				}
			}
		}
		for(int i = 0; i < arr.length ;i++) {
			System.out.print(arr[i] + " ");	
		}
    }
}

算法扩展：

1.时间复杂度：

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 C 和记录移动次数 M 均达到最小值

$Cmin = n-1,Mmin=0$

所以冒泡排序最好的时间复杂度为 O(n)

若初始文件是反序的，需要进行 n - 1 趟排序，每趟排序要进行 n - i 次关键字的比较 (1≤i≤n-1) 且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值

$Cmax=\frac {n(n-1)}{2} = O(n^2)$

$Mmax=\frac {3n(n-1)}{2} = O(n^2)$

所以冒泡排序最坏的时间复杂度是 O(n²)

2.实现方式：

#include<stdio.h>
int main(void) {
    int arr[10]={4,2,8,0,5,7,1,3,9,10};
    for(int i=0;i<9;i++) {
        for(int j=0;j<9-i;j++) {
            if(arr[j]>arr[j + 1]) {
                int temp =arr[j];
                arr[j]= arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    for(i=0;i<10;i++) {
        printf("%d ",arr[i]);
    }
}

C 语言实现冒泡排序示例代码 👆

#include <iostream>
using namespace std;
int main() {
	int arr[] = {4,2,8,0,5,7,1,3,9,10};
	int end = sizeof(arr) / sizeof(arr[0]) - 1;
	for (int i = 0; i < end; i++) {
		for (int j = 0; j < end - i; j++) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i <= end; i++) {
		cout << arr[i] << " ";
	}
	system("pause");
	return 0;
}

C++ 语言实现冒泡排序示例代码 👆

public class Demo{
	public static void main(String args []) {
		int [] arr = new int[10]{4,2,8,0,5,7,1,3,9,10};
		for(int i = 0;i < arr.length - 1;i ++) {
			for(int j = 0;j < arr.length - i - 1;j ++) {
				if(arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		for(int i = 0;i < arr.length;i ++) {
			Console.WriteLine(arr[i].ToString());
		}
	}
}

C# 语言实现冒泡排序示例代码 👆

def bubble(bubbleList):
    listLength = len(bubbleList)
    while listLength > 0:
        for i in range(listLength - 1):
            if bubbleList[i] > bubbleList[i+1]:
                bubbleList[i], bubbleList[i+1] = bubbleList[i+1], bubbleList[i]
        listLength -= 1
    print bubbleList
 
if __name__ == '__main__':
    bubbleList = [4,2,8,0,5,7,1,3,9,10]
    bubble(bubbleList)

Python 语言实现冒泡排序示例代码 👆

DATAS SEGMENT
    DATA1 DW 4,2,8,0,5,7,1,3,9,10
DATAS ENDS

CODES SEGMENT
    ASSUME CS:CODES,DS:DATAS
START:
    MOV AX,DATAS
    MOV DS,AX
    MOV CX,9
ONE: 					
	MOV SI,0			
	CMP CX,0			
	JE EXIT
	DEC CX				
	MOV BX,CX
	ADD BX,CX							
TWO:
	MOV AX,DATA1[SI]	
	CMP AX,DATA1[SI+2]	
	JLE THREE				
	XCHG AX,DATA1[SI+2]	
	XCHG AX,[SI]			
THREE:
	CMP SI,BX
	JE ONE
	ADD SI,2			
	JMP TWO
EXIT:
    MOV AH,4CH
    INT 21H
CODES ENDS
    END START

汇编 语言实现冒泡排序示例代码 👆

3.算法比较：