算法思想及步骤

1、比较相邻的元素，如果第一个比第二个大，那么交换他们的位置

2、对每一个相邻的元素做同样的比较，从开始到最后，这步做完，最后一个元素就是当前数组中最大的元素

比如，第一个和第二个比，如果第一个值大，那么交换，交换后，用新的第二个和第三个比.....

3、针对每个元素都重复步骤2的操作，这样，第一次找出最大的元素放到最后，第二次找到剩余最大的放到倒数第二个位置......

4、每执行一次步骤2，都会排序出一个元素，下一次都会少比较一次，直到没有任何需要比较的元素或者某次执行步骤2时，未发生任何交换。

代码实现（java版本）

public class BubbleSort { 	public static void bubbleSort(int[] arr) {		if (arr == null || arr.length == 0) {			return;		} 		int len = arr.length;		// 需要循环比较的最大次数，len - 1		for (int i = 1; i < len; i++) {			// 定义一个标识，如果当前比较轮次，没有发生任何交换，那么说明已经排序完成			boolean swap = true;			// 每次比较的元素个数，每轮都少比较一次			for (int j = 0; j < len - i; j++) {				int current = arr[j];				int next = arr[j + 1];				if (current > next) {					arr[j + 1] = current;					arr[j] = next;					swap = false;				}			}			if (swap) {				break;			}		}	}}

如果待排序序列已经是排好序的了，那么时间复杂度为O(n)，如果是一个完全倒序的序列，那么时间复杂度为O(n2)，所以冒泡排序的平均时间复杂度为O(n2)，空间复杂度为O(1)。