# 排序 - 冒泡排序（Bubble Sort）

# 冒泡排序介绍

它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！

我们先分析第 1 趟排序

于是，第 1 趟排序完之后，数列 {20,40,30,10,60,50} 变成了 {20,30,10,40,50,60}。此时，数列末尾的值最大。

根据这种方法:

冒泡排序的时间复杂度是 O (N2)。假设被排序的数列中有 N 个数。遍历一趟的时间复杂度是 O (N)，需要遍历多少次呢？N-1 次！因此，冒泡排序的时间复杂度是 O (N2)。

冒泡排序是稳定的算法，它满足稳定算法的定义。算法稳定性 – 假设在数列中存在 a [i]=a [j]，若在排序之前，a [i] 在 a [j] 前面；并且排序之后，a [i] 仍然在 a [j] 前面。则这个排序算法是稳定的！

冒泡排序如何减少时间复杂度：

如果某次内部循环完全不交换，这意味着数组已经有序，我们可以在这个点上停止冒泡排序。

	/**
	* 冒泡排序最终版，减少时间复杂度
	* @author wspstart
	* @create 2023-01-23 21:04
	*/
	public class BubbleSort {

	public static void sort(int[] a){
	for (int i = a.length - 1; i > 0; i--) {
	boolean swapped = false;
	for (int j = 0; j < i; j++) {
	if (greater(a[j],a[j + 1])){
	exch(a,j,j+1);
	swapped = true;
	}
	}
	if (!swapped){
	break;
	}
	println(i,a);
	}
	}

	/**
	* 比较 v 元素是否大于 w 元素
	*
	* @param v
	* @param w
	* @return
	*/
	private static boolean greater( int v, int w) {
	return v > w;
	}

	/**
	* 数组元素 i 和 j 交换
	*
	* @param a
	* @param i
	* @param j
	*/
	private static void exch(int[] a, int i, int j) {
	int temp;
	temp = a[i];
	a[i] = a[j];
	a[j] = temp;
	}

	private static void println(int num, int[] a) {
	System.out.println("第" + num + "次循环" + Arrays.toString(a));
	}
	}

测试代码：