转载：算法：冒泡排序BubbleSort
原始链接：https://zhuanlan.zhihu.com/p/95702340
原文链接：https://zhuanlan.zhihu.com/p/95702340
冒牌排序算法时间复杂度最坏的情况是，最好的，说明冒泡排序是可以优化的，就看你有没有去发现。
冒泡排序算法的过程是两个元素比较的大小，是典型的交换排序算法。快速排序算法和鸡尾酒排序算法也属于交换排序。
排序方法
比较相邻的元素，判断是否符合要求，如果不符合就交换位置来达到排序的目的。
对每一对相邻元素做相同的工作，从开始第一对到结尾的最后一对，一次遍历之后，最后一个元素是最大（小）的数。
第二次遍历重复以上操作，因为最后一个元素已经确定位置，减少一次计算。以此类推。
示例
通过一个示例来理解基本的冒泡排序算法，假设当前我们有一个数组a，里面元素是：5，6，1，7，2，4，3
初始状态
视频动画
1_BubbleSort_冒泡排序_1.wmv
Code
package cn.study.sort;
import java.util.Arrays;
public class BubbleSort1 {
public static void bubbleSortOne(int[] array){
for(int i = 0; i < array.length - 1; i++){
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j + 1]){
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
System.out.println("发生交换：" + Arrays.toString(array));
}
}
System.out.println(i + 1 + "次遍历：" + Arrays.toString(array));
}
}//end of method bubbleSortOne
public static void main(String[] args) {
int[] array = {5,6,1,7,2,4,3};
System.out.println("初始状态：" + Arrays.toString(array));
bubbleSortOne(array);
System.out.println(Arrays.toString(array));
}
}
Result
初始状态[5, 6, 1, 7, 2, 4, 3]
发生交换[5, 1, 6, 7, 2, 4, 3]
发生交换[5, 1, 6, 2, 7, 4, 3]
发生交换[5, 1, 6, 2, 4, 7, 3]
发生交换[5, 1, 6, 2, 4, 3, 7]
1次遍历：[5, 1, 6, 2, 4, 3, 7]
发生交换[1, 5, 6, 2, 4, 3, 7]
发生交换[1, 5, 2, 6, 4, 3, 7]
发生交换[1, 5, 2, 4, 6, 3, 7]
发生交换[1, 5, 2, 4, 3, 6, 7]
2次遍历：[1, 5, 2, 4, 3, 6, 7]
发生交换[1, 2, 5, 4, 3, 6, 7]
发生交换[1, 2, 4, 5, 3, 6, 7]
发生交换[1, 2, 4, 3, 5, 6, 7]
3次遍历：[1, 2, 4, 3, 5, 6, 7]
发生交换[1, 2, 3, 4, 5, 6, 7]
4次遍历：[1, 2, 3, 4, 5, 6, 7]
5次遍历：[1, 2, 3, 4, 5, 6, 7]
6次遍历：[1, 2, 3, 4, 5, 6, 7]
优化
可以发现，我们到第4次遍历的时候，发现已经排序完了，但是代码还是会继续判断是否符合要求。
仔细看看，第4次遍历之前还有一次元数位置交换，第5次遍历之前已经没有了交换。
所以我们可以设置一个标志位，用来表示当前i+1次是否还有交换，如果有就进行下一趟遍历，如果没有，则说明当前数组已经排完序，没有再进行比较的判断了。
Code
package cn.study.sort;
import java.util.Arrays;
public class BubbleSort1 {
public static void bubbleSortOne(int[] array){
for(int i = 0; i < array.length - 1; i++){
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j + 1]){
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
System.out.println("发生交换：" + Arrays.toString(array));
}
}
System.out.println(i + 1 + "次遍历：" + Arrays.toString(array));
}
}//end of method bubbleSortOne
//设置一个标志位，用来表示当前i+1次是否还有交换，如果有就进行下一趟遍历，如果没有，则说明当前数组已经排完序，没有再进行比较的判断了。
public static void bubbleSortTwo(int[] array){
for(int i = 0; i < array.length - 1; i++){
boolean flag = true;
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j + 1]){
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
flag = false;
System.out.println("发生交换：" + Arrays.toString(array));
}
}
if(flag){break;}
System.out.println(i + 1 + "次遍历：" + Arrays.toString(array));
}
}//end of method bubbleSortTwo
public static void main(String[] args) {
int[] array = {5,6,1,7,2,4,3};
System.out.println("初始状态：" + Arrays.toString(array));
// bubbleSortOne(array);
bubbleSortTwo(array);
System.out.println(Arrays.toString(array));
}
}
Result
初始状态[5, 6, 1, 7, 2, 4, 3]
发生交换[5, 1, 6, 7, 2, 4, 3]
发生交换[5, 1, 6, 2, 7, 4, 3]
发生交换[5, 1, 6, 2, 4, 7, 3]
发生交换[5, 1, 6, 2, 4, 3, 7]
1次遍历：[5, 1, 6, 2, 4, 3, 7]
发生交换[1, 5, 6, 2, 4, 3, 7]
发生交换[1, 5, 2, 6, 4, 3, 7]
发生交换[1, 5, 2, 4, 6, 3, 7]
发生交换[1, 5, 2, 4, 3, 6, 7]
2次遍历：[1, 5, 2, 4, 3, 6, 7]
发生交换[1, 2, 5, 4, 3, 6, 7]
发生交换[1, 2, 4, 5, 3, 6, 7]
发生交换[1, 2, 4, 3, 5, 6, 7]
3次遍历：[1, 2, 4, 3, 5, 6, 7]
发生交换[1, 2, 3, 4, 5, 6, 7]
4次遍历：[1, 2, 3, 4, 5, 6, 7]
好了这是第一次的优化，减少了计算次数。看上面的执行过程，你觉得还有什么办法使得时间复杂度尽可能少一点呢？
优化，还能再继续优化
我觉得还能再继续优化，为了更直白一点，这次我们换一个数组，数组元素为：4, 3, 2, 1, 5, 6, 7
Code
package cn.study.sort;
import java.util.Arrays;
public class BubbleSort1 {
public static void bubbleSortOne(int[] array){
for(int i = 0; i < array.length - 1; i++){
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j + 1]){
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
System.out.println("发生交换：" + Arrays.toString(array));
}
}
System.out.println(i + 1 + "次遍历：" + Arrays.toString(array));
}
}//end of method bubbleSortOne
//设置一个标志位，用来表示当前i+1次是否还有交换，如果有就进行下一趟遍历，如果没有，则说明当前数组已经排完序，没有再进行比较的判断了。
public static void bubbleSortTwo(int[] array){
for(int i = 0; i < array.length - 1; i++){
boolean flag = true;
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j + 1]){
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
flag = false;
System.out.println("发生交换：" + Arrays.toString(array));
}
System.out.println("你在浪费计算吗？");
}
if(flag){break;}
System.out.println(i + 1 + "次遍历：" + Arrays.toString(array));
}
}//end of method bubbleSortTwo
public static void main(String[] args) {
// int[] array = {5,6,1,7,2,4,3};
int[] array = {4,3,2,1,5,6,7};
System.out.println("初始状态：" + Arrays.toString(array));
// bubbleSortOne(array);
bubbleSortTwo(array);
System.out.println(Arrays.toString(array));
}
}
Result
看到上面的结果可以看出一个问题，里面的for循环明明已经归位了，又增加了不必要的计算次数。问题是在于j < array.length – i – 1。
我们可以这样解决，进行第1次遍历之前，记录交换元素的最后一个位置lastPostion。交换后的元素后一个肯定要比前面一个元素大，lastPostion就记录前面一个元素就可以了。
进行一次遍历之后，lastPostion的记录有了，里面的for循环进行下标0到lastPostion的数组就可以了，lastPostion后面的一串数组由于前面第一次循环验证过了，没有任何交换的元素 ，说明也是排好序的。
视频动画
1_BubbleSort_冒泡排序_2.wmv
Code
package cn.study.sort;
import java.util.Arrays;
public class BubbleSort1 {
public static void bubbleSortOne(int[] array){
for(int i = 0; i < array.length - 1; i++){
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j + 1]){
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
System.out.println("发生交换：" + Arrays.toString(array));
}
}
System.out.println(i + 1 + "次遍历：" + Arrays.toString(array));
}
}//end of method bubbleSortOne
//设置一个标志位，用来表示当前i+1次是否还有交换，如果有就进行下一趟遍历，如果没有，则说明当前数组已经排完序，没有再进行比较的判断了。
public static void bubbleSortTwo(int[] array){
for(int i = 0; i < array.length - 1; i++){
boolean flag = true;
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j + 1]){
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
flag = false;
System.out.println("发生交换：" + Arrays.toString(array));
}
System.out.println("你在浪费计算吗？");
}
if(flag){break;}
System.out.println(i + 1 + "次遍历：" + Arrays.toString(array));
}
}//end of method bubbleSortTwo
//进行第1次遍历之前，记录交换元素的最后一个位置lastPostion。交换后的元素后一个肯定要比前面一个元素大，lastPostion就记录前面一个元素就可以了。
//进行一次遍历之后，lastPostion的记录有了，里面的for循环进行下标0到lastPostion的数组就可以了，lastPostion后面的一串数组由于前面第一次循环验证过了，没有任何交换的元素 ，说明也是排好序的。
public static void bubbleSortThree(int[] array){
int lastPosition = 0;//记录最后一个位置
int len = array.length - 1;
for(int i = 0; i < array.length - 1; i++){
boolean flag = true;
for(int j = 0; j < len; j++){
if(array[j] > array[j + 1]){
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
flag = false;
lastPosition = j;
System.out.println("发生交换：" + Arrays.toString(array));
}
System.out.println("你在浪费计算吗？");
}
len = lastPosition;
if(flag){break;}
System.out.println(i + 1 + "次遍历：" + Arrays.toString(array));
}
}//end of method bubbleSortThree
public static void main(String[] args) {
// int[] array = {5,6,1,7,2,4,3};
int[] array = {4,3,2,1,5,6,7};
System.out.println("初始状态：" + Arrays.toString(array));
// bubbleSortOne(array);
// bubbleSortTwo(array);
bubbleSortThree(array);
System.out.println(Arrays.toString(array));
}
}
Result
