一、简述
冒泡排序(Bubble Sort)是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果二者的顺序(如从大到小、首字母从A到Z)错误就交换。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。这个算法名字的由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列)，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
二、冒泡排序算法原理
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
三、冒泡排序算法分析
四、冒泡排序算法描述
public static void bubbleSort(int[] arr) {
for(int i =0;i<arr.length-1;i++) {
for(int j=0;j<arr.length-i-1;j++) {//-1为了防止溢出
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
注意：
这里涉及到一交换函数，交换函数有很多种写法，基本的写法：
void swap(int a,int b) {
int temp = a;
a = b;
b = temp;
}
那么不用中间变量如何交换两个数？这时我们可以用位运算：
void swap(int a,int b) {
a = a ^ b;
b = b ^ a;
a = a ^ b;
}
一般建议用第一种方法。
不过当需要排序的数组处于基本有序时，第一种做法由于做出许多不必要的查找判断，降低了代码的执行效率，那么可不可以优化一下呢？答案是肯定的，我们可以加个标识flag，用来判断本次排序中是否需要发生交换，如果没有发生交换，说明排序已经完成了，无需再做交换处理。
public static void bubbleSort(int[] arr, int n) {
int i,j;
int flag; // 标识
for (i=n-1; i>0; i--) {
flag = 0; // 初始化标识为0
// 将arr[0...i]中最大的数据放在末尾
for (j=0; j<i; j++) {
if (arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
flag = 1; // 若发生交换，则设标识为1
}
}
if (flag == 0){
break; // 若没发生交换，则说明数列已有序。
}
}
}
冒泡排序法基本来说还是挺不错的，数据规模不大时，还是推荐使用的，但相对于其他的排序算法（譬如快速排序）效率还是有些不足。
五、例子：待排序数组：int[] array={7,4,8,3,9,2};
第1️⃣趟排序：
第一次排序：7和4比较，7大于4，交换位置： 4 7 8 3 9 2
第二次排序：7和8比较，7小于8，不交换位置：4 7 8 3 9 2
第三次排序：8和3比较，8大于3，交换位置： 4 7 3 8 9 2
第四次排序：8和9比较，8小于9，不交换位置：4 7 3 8 9 2
第五次排序：9和2比较：9大于2，交换位置： 4 7 3 8 2 9
第一趟总共进行了5次比较， 排序结果： 4 7 3 8 2 9
第2️⃣趟排序：
第一次排序：4和7比较，4小于7，不交换位置：4 7 3 8 2 9
第二次排序：7和3比较，7大于3，交换位置： 4 3 7 8 2 9
第三次排序：7和8比较，7小于8，不交换位置：4 3 7 8 2 9
第四次排序：8和2比较，8大于2，交换位置： 4 3 7 2 8 9
第二趟总共进行了4次比较， 排序结果： 4 3 7 2 8 9
第3️⃣趟排序：
第一次排序：4和3比较，4大于3，交换位置： 3 4 7 2 8 9
第二次排序：4和7比较，4小于7，不交换位置：3 4 7 2 8 9
第三次排序：7和2比较，7大于2，交换位置： 3 4 2 7 8 9
第三趟总共进行了3次比较， 排序结果： 3 4 2 7 8 9
第4️⃣趟排序：
第一次排序：3和4比较，3小于4，不交换位置：3 4 2 7 8 9
第二次排序：4和2比较，4大于2，交换位置： 3 2 4 7 8 9
第四趟总共进行了2次比较， 排序结果： 3 2 4 7 8 9
第5️⃣趟排序：
第一次排序：3和2比较，3大于2，交换位置： 2 3 4 7 8 9
