要点

冒泡排序是一种交换排序。
什么是交换排序呢？
交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。

算法思想

两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
假设有n个元素，则最差的情况下则需要n－1趟排序，每趟参与排序的元素个数＝n - 已经排序的趟数。好的情况趟数则在0～n这个范围内。

冒泡排序示意图

以上图为例，我们一起看下冒泡排序的实际流程：
假设有一个无序序列｛5，4，1，3，2｝
第一轮排序：通过两两相临比较，找到最小的数值 1，将其放在序列的第一位；
第二轮排序：通过两两相临比较，找到第二小的数值 2，将其放在序列的第二位；
第三轮排序：通过两两相邻比较，找到第三小的数值 3，将其放在序列的第三位；
……
每一轮排序，我们都能找到剩余未排序的最小数值，直至整个序列处于有序状态，排序结束。

若想将上面的流程转换为代码，我们则需要：

1 总共需要多少趟排序，则需要一个外部循环控制趟的次数;
每趟获得一个最小值，最后一个必然是最大值，因此坐标从0开始，到n-1;
2 每趟需要遍历多少元素，找到本趟中的最小值，则需要一个内部循环;
因为每趟排序我们都能找到剩余序列中的最小值，并排放在序列的前面位置，所以呢，我们每趟排序从后往前扫描，扫描到已经排好序的位置即可。因此坐标从n－1开始，直至已经排好序的位置。

算法分析

冒泡排序算法的性能

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好时间复杂度为O(N)。
若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax = N(N-1)/2 = O(N2)
Mmax = 3N(N-1)/2 = O(N2)
冒泡排序的最坏时间复杂度为O(N2)。
因此，冒泡排序的平均时间复杂度为O(N2)。
总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。
所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

优化

对冒泡排序常见的改进方法是加入标志性变量exchange，用于标志某一趟排序过程中是否有数据交换。
如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。

完整参考代码

package com.akathink.sort;
import java.util.ArrayList;
import java.util.List;
public class BubbleSort {
	/**
	 * 未优化的冒泡排序算法
	 * @param pDataList 待排序的无序序列
	 */
	public static void bubbleSort1(List<Integer> pDataList){
		//排序趟数
		for(int i = 0,size = pDataList.size() - 1;i < size;i++){
			//在剩余序列中获取最小值
			for(int j = pDataList.size() - 1;j > i;j--){//注意j是从后往前循环
				if(pDataList.get(j-1) > pDataList.get(j)){
					int temp = pDataList.get(j-1);
					pDataList.set(j-1, pDataList.get(j));
					pDataList.set(j, temp);
				}
			}
			System.out.format("第 %d 趟：\t", i);
			printAll(pDataList);
		}
	}
	/**
	 * 优化后的冒泡排序算法
	 * @param pDataList 待排序的无序序列
	 */
	public static void bubbleSort2(List<Integer> pDataList){
		boolean changeFlag = false;
		//排序趟数
		for(int i = 0,size = pDataList.size() - 1;i < size;i++){
			changeFlag = false;
			//在剩余序列中获取最小值
			for(int j = pDataList.size() - 1;j > i;j--){//注意j是从后往前循环
				if(pDataList.get(j-1) > pDataList.get(j)){
					int temp = pDataList.get(j-1);
					pDataList.set(j-1, pDataList.get(j));
					pDataList.set(j, temp);
					changeFlag = true;
				}
			}
			// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序
			if(!changeFlag){
				break;
			}
			System.out.format("第 %d 趟：\t", i);
			printAll(pDataList);
		}
	}
	public static void printAll(List<Integer> pDataList) {
		for(int value : pDataList){
			System.out.print(value + "\t");
		}
		 System.out.println();
	}
	public static void main(String[] args) {
		List<Integer> dataList = new ArrayList<>();
		dataList.add(5);
		dataList.add(4);
		dataList.add(1);
		dataList.add(3);
		dataList.add(2);
		System.out.print("排序前:\t");
		printAll(dataList);
		bubbleSort2(dataList);
		System.out.print("排序后:\t");
		printAll(dataList);
	}
}

运行结果

排序前:	  5	4	1	3	2
第 0 趟：	1	5	4	2	3
第 1 趟：	1	2	5	4	3
第 2 趟：	1	2	3	5	4
第 3 趟：	1	2	3	4	5
排序后:	  1	2	3	4	5

参考资料

《大话数据结构》
http://www.cnblogs.com/jingmoxukong/p/4302718.html

AkaThink

排序一：冒泡排序

要点