首页 > 代码库 > 冒泡排序
冒泡排序
目录：
1、为什么要用？（它的好处或优点）
2、原理是什么？（效果）
3、怎样去实现？（想马上看代码的同学点这里）
为什么要用？
1、时间复杂度： 平均情况 O(n2)、最坏情况O(n2)，最好情况O(n)
2、空间复杂度： O(1)
3、稳定性： 稳定
4、复杂度：简单 容易实现
适用场景： 有序部分放到后方，根据大小两两交换，每次遍历都可以将无序部分的最大值过滤到最后，直至完成排序，实现容易，稳定，空间占用少
不适用场景 ： 已排序数据在最后插入小数据
原理是什么？
例如 排序数组 [6 5 3 1 8 7 2 4]
第一次遍历
比较 [6 5 3 1 8 7 2 4]
需交换 [5 6 3 1 8 7 2 4]
比较 [5 6 3 1 8 7 2 4]
需交换 [5 3 6 1 8 7 2 4]
比较 [5 3 6 1 8 7 2 4]
需交换 [5 3 1 6 8 7 2 4]
比较 [5 3 1 6 8 7 2 4]
不需交换 [5 3 1 6 8 7 2 4]
比较 [5 3 1 6 8 7 2 4]
需交换 [5 3 1 6 7 8 2 4]
比较 [5 3 1 6 7 8 2 4]
需交换 [5 3 1 6 7 2 8 4]
比较 [5 3 1 6 7 2 8 4]
需交换 [5 3 1 6 7 2 4 8]
第二次遍历
。。。
可以看到第一次遍历已经把最大的放到最后，第二次遍历则不必再比较最后一个，这样一直遍历下去，可以想象如果最小的在最后，最多遍历 N-1（N为数组长度）次，即可排序完成。如果在本次遍历中没有交换动作，则表明已经排序完成，直接退出不用再遍历到 N-1次。
宏观效果：
怎样去实现？
java 实现代码：
class bubble_sort { public static void bubble(int[] arr) { int i, j, t,s; // t 交换时中间变量 , s 标示完成状态 for (i = 0; i < arr.length - 1; i++){ s = 0; for (j = 0; j < arr.length - 1 - i; j++){ if (arr[j] > arr[j + 1]) { s = 1; t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; printArray(arr); } } if(s == 0){ //发现 循环中已经没有交换操作了,代表已经完成排序,退出 return; } } } public static void main (String[] args) throws java.lang.Exception { int[] arr = {6,5,3,1,8,7,2,4}; printArray(arr); bubble(arr); } public static void printArray(int[] arr){ for(int i : arr){ System.out.print(i+" "); } System.out.println(); } }
输出结果 ：
6 5 3 1 8 7 2 4
5 6 3 1 8 7 2 4
5 3 6 1 8 7 2 4
5 3 1 6 8 7 2 4
5 3 1 6 7 8 2 4
5 3 1 6 7 2 8 4
5 3 1 6 7 2 4 8
3 5 1 6 7 2 4 8
3 1 5 6 7 2 4 8
3 1 5 6 2 7 4 8
3 1 5 6 2 4 7 8
1 3 5 6 2 4 7 8
1 3 5 2 6 4 7 8
1 3 5 2 4 6 7 8
1 3 2 5 4 6 7 8
1 3 2 4 5 6 7 8
1 2 3 4 5 6 7 8
在线测试地址 ：https://www.shucunwang.com/RunCode/java/#id/954b104d0c9dbb6b89f5bac5189f10af
开源代码地址 ：https://git.oschina.net/ITxiaoyan/SortAlgorithm
2017-03-25
冒泡排序