什么是冒泡排序
这里引用一下百度百科上的定义：
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序在实际工作中用的并不多，多是面试题中会遇到。
下面用java代码来实现：
基本写法
为了看到后面优化后的效果，我加了count 和 num l两个变量来分布统计外循环和内循环的次数
/**
* 原始的冒泡排序
* @param values
*/
public static void bubbleSort(int[] values) {
System.out.println("排序前：" + Arrays.toString(values));
int tmp;// 循环外创建变量，减少垃圾产生，提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环，n 个元素，最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
count ++;
// 内层循环， 每一次都从开始两个元素开始两两比较到最后
for (int j = 0; j < values.length - 1; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
}
num ++;
}
}
System.out.println("排序后：" + Arrays.toString(values));
System.out.println("比较趟数："+count + ",比较次数：" + num);
}
优化后写法
/**
* 优化了比较次数的冒泡排序
* @param values
*/
public static void bubbleSort2(int[] values) {
System.out.println("排序前：" + Arrays.toString(values));
int tmp; // 循环外创建变量，减少垃圾产生，提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环，n 个元素，最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
count ++;
// 内层循环， 每一次都从开始两个元素开始两两比较到最后
/* 每一趟循环都可以找你最大的数，内循环可以比上一趟循环减少一次比较 */
for (int j = 0; j < values.length - 1 - i; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
}
num ++;
}
}
System.out.println("排序后：" + Arrays.toString(values));
System.out.println("比较趟数："+count + ",比较次数：" + num);
}
显然，每一趟循环都可以找你最大的数，内循环可以比上一趟循环减少一次，面试时写成这样基本OK了。
终极版本
实际中，用来比较的数据，可能就只有几个位置是无序的，如果也按照上面的写法进行 length -1 次循环就显得有点死板了。
因此我们可以假设数组已经排好序了，给程序一个标记变量，如果标记变量显示数组已排好序，则可以跳出循环。
/**
* 冒泡排序终极写法
* @param values
*/
public static void bubbleSort3(int[] values) {
System.out.println("排序前：" + Arrays.toString(values));
int tmp;// 循环外创建变量，减少垃圾产生，提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环，n 个元素，最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
// 定义一个boolean 值，标记数组是否达到有序状态
boolean flag = true;
count ++;
// 内层循环， 每一次都从开始两个元素开始两两比较到最后
/* 每一趟循环都可以找你最大的数，内循环可以比上一趟循环减少一次比较 */
for (int j = 0; j < values.length - 1 - i; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
// 如果本趟发生了交换，表明数组还是无序，需要进入下一轮循环
flag = false;
}
num ++;
}
// 根据标记的布尔值判断数组是否达到有序状态，如有序，则退出循环
if( flag) {
break;
}
}
System.out.println("排序后：" + Arrays.toString(values));
System.out.println("比较趟数："+count + ",比较次数：" + num);
}
源码及测试
package com.xzlf.sort;
import java.util.Arrays;
public class TestSort {
public static void main(String[] args) {
int[] arr = {1,341,33,22,88,99,100};
int[] arr2 = {1,341,33,22,88,99,100};
int[] arr3 = {1,341,33,22,88,99,100};
bubbleSort(arr);
System.out.println("==================");
bubbleSort2(arr2);
System.out.println("==================");
bubbleSort3(arr3);
}
/**
* 原始的冒泡排序
* @param values
*/
public static void bubbleSort(int[] values) {
System.out.println("排序前：" + Arrays.toString(values));
int tmp;// 循环外创建变量，减少垃圾产生，提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环，n 个元素，最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
count ++;
// 内层循环， 每一次都从开始两个元素开始两两比较到最后
for (int j = 0; j < values.length - 1; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
}
num ++;
}
}
System.out.println("排序后：" + Arrays.toString(values));
System.out.println("比较趟数："+count + ",比较次数：" + num);
}
/**
* 优化了比较次数的冒泡排序
* @param values
*/
public static void bubbleSort2(int[] values) {
System.out.println("排序前：" + Arrays.toString(values));
int tmp; // 循环外创建变量，减少垃圾产生，提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环，n 个元素，最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
count ++;
// 内层循环， 每一次都从开始两个元素开始两两比较到最后
/* 每一趟循环都可以找你最大的数，内循环可以比上一趟循环减少一次比较 */
for (int j = 0; j < values.length - 1 - i; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
}
num ++;
}
}
System.out.println("排序后：" + Arrays.toString(values));
System.out.println("比较趟数："+count + ",比较次数：" + num);
}
/**
* 冒泡排序终极写法
* @param values
*/
public static void bubbleSort3(int[] values) {
System.out.println("排序前：" + Arrays.toString(values));
int tmp;// 循环外创建变量，减少垃圾产生，提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环，n 个元素，最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
// 定义一个boolean 值，标记数组是否达到有序状态
boolean flag = true;
count ++;
// 内层循环， 每一次都从开始两个元素开始两两比较到最后
/* 每一趟循环都可以找你最大的数，内循环可以比上一趟循环减少一次比较 */
for (int j = 0; j < values.length - 1 - i; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
// 如果本趟发生了交换，表明数组还是无序，需要进入下一轮循环
flag = false;
}
num ++;
}
// 根据标记的布尔值判断数组是否达到有序状态，如有序，则退出循环
if( flag) {
break;
}
}
System.out.println("排序后：" + Arrays.toString(values));
System.out.println("比较趟数："+count + ",比较次数：" + num);
}
}
上面代码运行结果：
@[TOC](Java/java基础)