冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
一、算法原理
冒泡排序算法的运作如下：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、 针对所有的元素重复以上的步骤，除了最后一个。
4、 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
二、算法分析
时间复杂度
算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
算法演练
下面动画演示从最后一个数开始和上一个数比较，如果小于上一个数就交换位置。
ps:读者也可以自己打开下面的链接，自己设定要排序的数组，进行排序演练
冒泡排序动画演示（http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/maopaopaixu.htm）
三、代码实现
public class BubbleSortTest {
/**
* 冒泡排序
* @param source
* 要进行排序的数组
*/
public static void bubbleSort(int[] source) {
int length = source.length;
for (int i = 0; i < length - 1; i++) { //N个数需N-1趟,每趟完成之后,较大元素将冒到数组最末端
for (int j = 0; j < length - 1 - i; j++) { //每趟需要比较N-i次比较
if (source[j] > source[j + 1]) {
swap(source, j, j + 1);
}
System.out.print("\n外循环第" + (i + 1) + "次,内循环第" + (j + 1)
+ "次,排序结果：");
printArray(source);
}
System.out.println("");
}
}
/**
* 交换x、y下标指向的值
*
* @param source
* 要进行交换的数组
* @param x
* 数组下标x
* @param y
* 数组下标x
*/
private static void swap(int[] source, int x, int y) {
int temp = source[x];
source[x] = source[y];
source[y] = temp;
}
/**
* 遍历数组然后打印
* @param source 要打印的数组
*/
private static void printArray(int[] source) {
for (int i = 0; i < source.length; i++) {
System.out.print("\t" + source[i]);
}
}
public static void main(String[] args) {
int[] source = { 24, 19, 26, 39, 36, 7, 31, 29, 38, 23 };
System.out.println("排序前：");
printArray(source);
System.out.println("\n");
bubbleSort(source);
System.out.println("\n\n排序后：");
printArray(source);
}
}
四、运行结果
排序前： 24 19 26 39 36 7 31 29 38 23 外循环第1次,内循环第1次,排序结果： 19 24 26 39 36 7 31 29 38 23 外循环第1次,内循环第2次,排序结果： 19 24 26 39 36 7 31 29 38 23 外循环第1次,内循环第3次,排序结果： 19 24 26 39 36 7 31 29 38 23 外循环第1次,内循环第4次,排序结果： 19 24 26 36 39 7 31 29 38 23 外循环第1次,内循环第5次,排序结果： 19 24 26 36 7 39 31 29 38 23 外循环第1次,内循环第6次,排序结果： 19 24 26 36 7 31 39 29 38 23 外循环第1次,内循环第7次,排序结果： 19 24 26 36 7 31 29 39 38 23 外循环第1次,内循环第8次,排序结果： 19 24 26 36 7 31 29 38 39 23 外循环第1次,内循环第9次,排序结果： 19 24 26 36 7 31 29 38 23 39 外循环第2次,内循环第1次,排序结果： 19 24 26 36 7 31 29 38 23 39 外循环第2次,内循环第2次,排序结果： 19 24 26 36 7 31 29 38 23 39 外循环第2次,内循环第3次,排序结果： 19 24 26 36 7 31 29 38 23 39 外循环第2次,内循环第4次,排序结果： 19 24 26 7 36 31 29 38 23 39 外循环第2次,内循环第5次,排序结果： 19 24 26 7 31 36 29 38 23 39 外循环第2次,内循环第6次,排序结果： 19 24 26 7 31 29 36 38 23 39 外循环第2次,内循环第7次,排序结果： 19 24 26 7 31 29 36 38 23 39 外循环第2次,内循环第8次,排序结果： 19 24 26 7 31 29 36 23 38 39 外循环第3次,内循环第1次,排序结果： 19 24 26 7 31 29 36 23 38 39 外循环第3次,内循环第2次,排序结果： 19 24 26 7 31 29 36 23 38 39 外循环第3次,内循环第3次,排序结果： 19 24 7 26 31 29 36 23 38 39 外循环第3次,内循环第4次,排序结果： 19 24 7 26 31 29 36 23 38 39 外循环第3次,内循环第5次,排序结果： 19 24 7 26 29 31 36 23 38 39 外循环第3次,内循环第6次,排序结果： 19 24 7 26 29 31 36 23 38 39 外循环第3次,内循环第7次,排序结果： 19 24 7 26 29 31 23 36 38 39 外循环第4次,内循环第1次,排序结果： 19 24 7 26 29 31 23 36 38 39 外循环第4次,内循环第2次,排序结果： 19 7 24 26 29 31 23 36 38 39 外循环第4次,内循环第3次,排序结果： 19 7 24 26 29 31 23 36 38 39 外循环第4次,内循环第4次,排序结果： 19 7 24 26 29 31 23 36 38 39 外循环第4次,内循环第5次,排序结果： 19 7 24 26 29 31 23 36 38 39 外循环第4次,内循环第6次,排序结果： 19 7 24 26 29 23 31 36 38 39 外循环第5次,内循环第1次,排序结果： 7 19 24 26 29 23 31 36 38 39 外循环第5次,内循环第2次,排序结果： 7 19 24 26 29 23 31 36 38 39 外循环第5次,内循环第3次,排序结果： 7 19 24 26 29 23 31 36 38 39 外循环第5次,内循环第4次,排序结果： 7 19 24 26 29 23 31 36 38 39 外循环第5次,内循环第5次,排序结果： 7 19 24 26 23 29 31 36 38 39 外循环第6次,内循环第1次,排序结果： 7 19 24 26 23 29 31 36 38 39 外循环第6次,内循环第2次,排序结果： 7 19 24 26 23 29 31 36 38 39 外循环第6次,内循环第3次,排序结果： 7 19 24 26 23 29 31 36 38 39 外循环第6次,内循环第4次,排序结果： 7 19 24 23 26 29 31 36 38 39 外循环第7次,内循环第1次,排序结果： 7 19 24 23 26 29 31 36 38 39 外循环第7次,内循环第2次,排序结果： 7 19 24 23 26 29 31 36 38 39 外循环第7次,内循环第3次,排序结果： 7 19 23 24 26 29 31 36 38 39 外循环第8次,内循环第1次,排序结果： 7 19 23 24 26 29 31 36 38 39 外循环第8次,内循环第2次,排序结果： 7 19 23 24 26 29 31 36 38 39 外循环第9次,内循环第1次,排序结果： 7 19 23 24 26 29 31 36 38 39 排序后： 7 19 23 24 26 29 31 36 38 39
五、双向冒泡排序
算法原理：
传统冒泡算法原理
冒泡排序算法的运作如下：（从后往前）
-
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
-
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
-
针对所有的元素重复以上的步骤，除了最后一个。
-
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
双向冒泡算法原理
双向冒泡排序算法的运作如下：
-
传统冒泡气泡排序的双向进行，先让气泡排序由左向右进行，再来让气泡排序由右往左进行，如此完成一次排序的动作
-
使用left与right两个旗标来记录左右两端已排序的元素位置。
算法实例：
一个排序的例子如下所示：
排序前：45 19 77 81 13 28 18 1977 11
往右排序：19 45 77 13 28 18 19 7711 [81]
向左排序：[11] 19 45 77 13 28 1819 77 [81]
往右排序：[11] 19 45 13 28 18 19 [77 77 81]
向左排序：[11 13] 19 45 18 28 19 [77 77 81]
往右排序：[11 13] 19 18 28 19 [45 77 77 81]
向左排序：[11 13 18] 19 19 28 [45 77 77 81]
往右排序：[11 13 18] 19 19 [28 45 77 77 81]
向左排序：[11 13 18 19 19] [28 45 77 77 81]
如上所示，括号中表示左右两边已排序完成的部份，当left >= right时，则排序完成。
六、代码实现
package cn.fuxi.ms.sort;
public class DoubleBubbleSortTest {
/**
* 双向冒泡排序
* 在每一趟排序中，正向冒泡排序将剩余所有元素中较大的元素冒至剩余元素最右端，反向冒泡排序将剩余所有元素中较小的元素冒至剩余元素最左端
* @param source
* 要进行排序的数组
*/
public static void doubleBubbleSort(int[] source) {
int length = source.length;
for (int i = 0, j; i < length / 2; i++) { // N个数需N/2趟
for (j = i; j < length - 1 - i; j++) { // 每趟需要比较N-i次比较
if (source[j] > source[j + 1]) {
swap(source, j, j + 1);
}
System.out.println("第" + (i + 1) + "次正向冒泡,排序结果：");
printArray(source);
}
System.out.println();
// 添加一层循环,同时从右至左,则每当此for循环结束,较小的数往左边冒出
for (--j; j > i; j--) {
if (source[j - 1] > source[j]) {
swap(source, j - 1, j);
}
System.out.println("第" + (i + 1) +"次反向冒泡,排序结果：");
printArray(source);
}
System.out.println("");
}
}
/**
* 交换x、y下标指向的值
*
* @param source
* 要进行交换的数组
* @param x
* 数组下标x
* @param y
* 数组下标x
*/
private static void swap(int[] source, int x, int y) {
int temp = source[x];
source[x] = source[y];
source[y] = temp;
}
/**
* 遍历数组然后打印
*
* @param source
* 要打印的数组
*/
private static void printArray(int[] source) {
for (int i = 0; i < source.length; i++) {
System.out.print("\t" + source[i]);
}
System.out.println();
}
public static void main(String[] args) {
int[] source = { 24, 19, 26, 39, 36, 7, 31, 29, 38, 23 };
System.out.println("排序前：");
printArray(source);
doubleBubbleSort(source);
System.out.println("\n\n排序后：");
printArray(source);
}
}
七、打印结果
排序前： 24 19 26 39 36 7 31 29 38 23 第1次正向冒泡,排序结果： 19 24 26 39 36 7 31 29 38 23 第1次正向冒泡,排序结果： 19 24 26 39 36 7 31 29 38 23 第1次正向冒泡,排序结果： 19 24 26 39 36 7 31 29 38 23 第1次正向冒泡,排序结果： 19 24 26 36 39 7 31 29 38 23 第1次正向冒泡,排序结果： 19 24 26 36 7 39 31 29 38 23 第1次正向冒泡,排序结果： 19 24 26 36 7 31 39 29 38 23 第1次正向冒泡,排序结果： 19 24 26 36 7 31 29 39 38 23 第1次正向冒泡,排序结果： 19 24 26 36 7 31 29 38 39 23 第1次正向冒泡,排序结果： 19 24 26 36 7 31 29 38 23 39 第1次反向冒泡,排序结果： 19 24 26 36 7 31 29 23 38 39 第1次反向冒泡,排序结果： 19 24 26 36 7 31 23 29 38 39 第1次反向冒泡,排序结果： 19 24 26 36 7 23 31 29 38 39 第1次反向冒泡,排序结果： 19 24 26 36 7 23 31 29 38 39 第1次反向冒泡,排序结果： 19 24 26 7 36 23 31 29 38 39 第1次反向冒泡,排序结果： 19 24 7 26 36 23 31 29 38 39 第1次反向冒泡,排序结果： 19 7 24 26 36 23 31 29 38 39 第1次反向冒泡,排序结果： 7 19 24 26 36 23 31 29 38 39 第2次正向冒泡,排序结果： 7 19 24 26 36 23 31 29 38 39 第2次正向冒泡,排序结果： 7 19 24 26 36 23 31 29 38 39 第2次正向冒泡,排序结果： 7 19 24 26 36 23 31 29 38 39 第2次正向冒泡,排序结果： 7 19 24 26 23 36 31 29 38 39 第2次正向冒泡,排序结果： 7 19 24 26 23 31 36 29 38 39 第2次正向冒泡,排序结果： 7 19 24 26 23 31 29 36 38 39 第2次正向冒泡,排序结果： 7 19 24 26 23 31 29 36 38 39 第2次反向冒泡,排序结果： 7 19 24 26 23 31 29 36 38 39 第2次反向冒泡,排序结果： 7 19 24 26 23 29 31 36 38 39 第2次反向冒泡,排序结果： 7 19 24 26 23 29 31 36 38 39 第2次反向冒泡,排序结果： 7 19 24 23 26 29 31 36 38 39 第2次反向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第2次反向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次反向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次反向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次反向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第3次反向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第4次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第4次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第4次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第4次反向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第4次反向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 第5次正向冒泡,排序结果： 7 19 23 24 26 29 31 36 38 39 排序后： 7 19 23 24 26 29 31 36 38 39
==================================================================================================
作者：欧阳鹏 欢迎转载，与人分享是进步的源泉！
转载请保留原文地址：http://blog.csdn.net/ouyang_peng
==================================================================================================
