冒泡排序算法是一种基于比较的排序算法，每次冒泡过程，都会有一个数据确定位置。经过n次冒泡后，就有n个数据确定了位置。
如图所示，对数组[4,5,6,3,2,1]进行冒泡排序。
起初，按照最原始的想法，代码是这样写：
/** * 冒泡排序算法 * @param arr * @param n */ public static void bubbleSort(int[] arr,int n){ for (int i = 0; i < n ; i++) { for(int j=0;j<n-i-1;j++){ if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }拿数组[1,2,3,4,5,6]为例，这个比较极端完全是有序的，其实只需要一次冒泡就完成了，没有必要迭代n次，所以这个算法还可以改进，技巧就是当某次冒泡完全没有引起数据交换的时候，说明这个数组已经是有序了，程序即可退出了。
/** * 改进后冒泡排序算法 * @param arr * @param n */ public static void fixBubbleSort(int[] arr,int n){ for (int i = 0; i < n ; i++) { boolean ischange = false; for(int j=0;j<n-i-1;j++){ if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; ischange = true; } } if(!ischange){ return; } } } 冒泡排序是原地排序算法吗？所谓原地排序算法，就是空间复杂度为O(1)的算法，那么上边的算法不牵涉额外得到其他空间。所以是原地排序算法。
冒泡排序是稳定排序算法吗？
所谓稳定，指的是当数组中出现相同数值元素的时候，排序是否会造成相同数值元素相对位置的改变。可以看出在冒泡排序算法中，对于相同数值的元素我们并没有进行比较和交换位置，所以相同数值元素的相对位置不会发生改变，因此冒泡排序算法是稳定的排序算法。
冒泡排序算法的时间复杂度是多少？
在完全有序的情况下，最好的时间复杂度是O(n)，只需要1次冒泡。而在极端情况完全逆序，时间复杂度为O(n^2).
那么平均时间复杂度是多少？如果用概率论计算的话会非常复杂，这里介绍的是一种粗略估计的算法，牵涉到两个概念
有序度和逆序度。
有序度数组中具有有序关系的元素对的个数。有序元素对的定义：如果i<j,则a[i]<a[j]
问题：[4,5,6,3,2,1]的有序对有哪些？
答：(4,5)、（5,6）、（4,6），所以有序度为3.
问题：[6,5,4,3,2,1]的有序对有哪些？
答：不存在，所以有序度为0.
问题：[1,2,3,4,5,6]的有序对有哪些？
答：(1,2)、（1,3）、（1,4）、（1，5）、（1,6）、（2,3）、（2,4）、（2，5）、（2,6）、（3,4）、（3，5）、（3,6）、（4,5）、（4,6）、（5,6），所以有序度为15，也就是n(n-1)/2，这就是完全有序时满有序度的计算公式。
逆序度数组中具有逆序关系的元素对的个数。逆序元素对的定义：如果i<j,则a[i]>a[j]
有序度、逆序度的关系【 有序度 + 逆序度 = 满有序度 】
其实，排序就是增加有序度的过程，一直到有序度等于满有序度，而逆序度为0.
排序过程每交换一次，有序度加1，逆序度减1，比如刚开始原数组的有序度为x，那么逆序度=n(n-1)/2-x.也就是最终有序需要交换的次数。如果初始有序度x=0，那就是最坏的情况，逆序度为n(n-1)/2；如果有序度x为n(n-1)/2,那这就是最好的情况，逆序度为0，根本不需要交换。因此，可以取一个初始有序度不好也不坏的情况x=n(n-1)/4,最终交换的次数，即逆序度就等于n(n-1)/4,换算成时间复杂度就是O(n^2).