[数据结构与算法]排序算法之冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

基本思想： 将待排序的序列元素依次两两进行比较按照从小到大(或从大到小)排序，如果前面一个数比后面的数大则进行交换。N个元素经过N - 1次可以比较可以选出该序列最大的数，再从N - 1个元素中选出次大的数。。。如此下去则可以将整个序列排好序。

动图：

时间复杂度：
最好时间复杂度：若初始数据的状态是正序的,一趟扫描即可完成排序比较次数C = n - 1,移动次数M = 0均达到最小值
最坏时间复杂度：若初始数据的状态是逆序的, 需要进行 趟排序。每趟排序要进行 次关键字的比较(1≤i≤n-1)
且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：C = n(n-1)/2 = O(n^2) M = O(N^2)
平均时间复杂度：O(n^2)

空间复杂度：O(1)

算法的稳定性： 如果 a = b， a原本在b的前面， 排序之后， a仍然在b的前面， 那么这个排序算法就是稳定的。显然冒泡排序算法是稳定的。

优化：
如1 2 3 4 5已经有序的就不需要在进行第二趟比较了；1 2 3 5 4 第一堂比较后1 2 3 4 5第二趟1 2 3 4 没有数据交换说明有序的了直接break。

代码演示：

/**
 * @Author huang.bX
 * @Date 2022/7/23
 */
public class BubbleSort {
    public static void main(String[] args){
        int[] array = new int[]{12,19,89,7,51,80,80};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(array));
        bubbleSort(array);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(array));
    }
    public static void bubbleSort(int[] arr){
        //如果在某一次冒泡排序中,没有完成数据的交换,则说明数组已经有序
        boolean flag = true;
        for(int i = 0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1-i;j++){
                if (arr[j]>arr[j+1]){
                    flag = false;
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
            if (flag){
                break;
            }
        }
    }
}

测试结果：

常见数据结构与算法动态图演示：
动图演示