冒泡排序

关注
发布于: 2020 年 06 月 23 日
﻿
原理是相邻的两个元素进行比较，如果满足右边的值比左边的值小则交换这两者的位置。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
﻿
如果对数组8,5,1,5,3,2,4进行冒泡排序则第一次冒泡排序的过程：
第一次冒泡排序过程
﻿
整个冒泡排序算法的过程演示：
冒泡排序全过程演示
﻿
用java代码实现上面的演示过程：
package wjchenge.arithmetic;
import java.util.Arrays;
/**
 * 冒泡排序
 * @author wjchenge
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] a = new int[]{8,5,1,5,3,2,4};
        System.out.println(Arrays.toString(a));
        BubbleSort.bubbleSort(a);
        System.out.println(Arrays.toString(a));
    }
    public static void bubbleSort(int[] a) {
        if (a == null || a.length == 0) return;
        int length = a.length;
        //冒泡排序主要就是比较和交换（最后一个元素不需要比较）
        for (int i = 0; i < length - 1; ++i) {
            for (int j = 0; j < length - i - 1; ++j) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                }
            }
        }
    }
    public static void swap(int[] a, int i, int j) {
        if (a[i] != a[j]) {
            a[i] = a[i] ^ a[j];
            a[j] = a[i] ^ a[j];
            a[i] = a[i] ^ a[j];
        }
    }
}
﻿
最后几步冒泡排序动态演示图：
﻿
在最后几步的时候数组已经有序则不需要再执行比较操作了，所以存在优化思路是如果一次冒泡的过程中没有发生数据交换操作则说明数据已经有序则提前停止后续的冒泡操作。一种极端的情况是数组本身有序则执行一次冒泡排序就可以了，时间复杂度变成O(n)
﻿
public static void bubbleSort(int[] a) {
        if (a == null || a.length == 0) return;
        int length = a.length;
        //提前退出冒泡排序标识
        boolean flag = true;
        //冒泡排序主要就是比较和交换（最后一个元素不需要比较）
        for (int i = 0; i < length - 1; ++i) {
            for (int j = 0; j < length - i - 1; ++j) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    //如果存在交换则不提前退出
                    flag = false;
                }
            }
            //提前退出
            if (flag) {
                break;
            }
        }
    }
﻿
最后总结：
﻿
 冒泡排序是一种稳定的排序算法（比如一组数组8,5,1,5,3,2,4按照从小到大排序后为1,2,3,4,5,5,8。如果排序后两个5的前后顺序没有发生变化则是稳定的排序算法，反之则是不稳定的排序算法。）
 冒泡排序的时间复杂度是O（n²）
﻿