冒泡排序是一种典型的交换排序方式。基本思想是： 无序区中相邻两个记录比较和位置交换，使得最小记录如气泡一样逐渐往上浮 冒泡排序每趟产生的有序区一定是全局有序区。
冒泡排序算法：
public void bubbleSort(int[] array) { int n = array.length; for (int i = 0; i < n - 1; i++) { for (int j = n - 1; j > i; j--) { if (array[j] < array[j - 1]) { int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } }对冒泡算法进行改进：若某一趟比较中没有任何记录的交换，则表示所有记录都已经排好序。因此用一个标记，来标记是否进行了交换。 冒泡排序改进：
public void bubbleSort(int[] array) { int n = array.length; for (int i = 0; i < n - 1; i++) { boolean exchange = false; for (int j = n - 1; j > i; j--) { if (array[j] < array[j - 1]) { int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; exchange = true; } } if (!exchange) return; } }在第一步优化的基础上发进一步思考：如果R[0..i]已是有序区间，上次的扫描区间是R[i..n]，记上次扫描时最后 一次执行交换的位置为lastSwapPos，则lastSwapPos在i与n之间，不难发现R[i..lastSwapPos]区间也是有序的，否则这个区间也会发生交换；所以下次扫描区间就可以由R[i..n] 缩减到[lastSwapPos..n] 最终改进
public void bubbleSort(int[] array) { int n = array.length; int lastSwapPos = 0, lastSwapPosTemp = 0; for (int i = 0; i < n - 1; i++) { lastSwapPos = lastSwapPosTemp; for (int j = n - 1; j > lastSwapPos; j--) { if (array[j] < array[j - 1]) { int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; lastSwapPosTemp = j; } } if (lastSwapPos == lastSwapPosTemp) return; } }