简介

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。以升序为例。顺序轮序数组内元素。依次比较两个相邻的元素，如果顺序错误就交换位置。比较过程最大值就像泡泡一样从左往右慢慢浮到最右侧。每轮遍历后右侧元素为最大值。 共进行n轮轮序，最终排序完成。

文章中使用的动画网站地址，限 pc: http://www.donghuasuanfa.com/sort

https://blog..net/ww753951/article/details/106862328

代码示例

public static void bubbleSort(int arr[]) {
        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]) {
                    int temp = arr[j];                     
                    arr[j]=arr[j+1];      
                    arr[j+1]=temp;
                }
            }    
        }
    }

排序过程

下图所示为升序排序。首先比较13和43，因为13小于43，所以无需更换位置。然后比较43和31，因为43大于31，所以更换位置，更换后满足数组升序。最后再比较43和20，因为43大于20，所以更换位置。此过程为一轮比较，比较后保证最右侧为最大值。 共需要重复上述n次比较，才能保证数组整体为升序。

时间复杂度

最差时间复杂度&平均时间复杂度

每轮比较的过程是比较相邻的两个元素。此过程的时间复杂度为N。每轮比较后找出最大的一个元素。然后共比较N轮。所以时间复杂度为： O ( N 2 ) O(N^2) O(N2)

最优时间复杂度

说明

最优时间复杂度为 O(N) 。算法需要优化。 设置一个全局变量是否交换过位置。在第一次循环后判断如果没有进行过交换处理，则跳出循环。

代码示例

public static void bubbleSort(int arr[]) {
        boolean change = false;
        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]) {
                    int temp = arr[j];                     
                    arr[j]=arr[j+1];      
                    arr[j+1]=temp;
                    change = true;
                }
            }    
            if(! change){
                break;
            }
        }
    }

其中 change 变量为变化变量。如果 交换过位置则设置为true。循环结束后判断change变量是否为 false。如果为false，则未交换过位置，说明数组为已排序数组。可结束方法。

动画示例

空间复杂度

空间复杂度: O(1) 。 冒泡排序为交换排序，当两个元素大小不相同时，俩个元素交换位置，无需额外空间，所以空间复杂度为 O(1)。

稳定性

两个元素的值相同时如果最终排序完成后位置不变，则为稳定排序，如果位置变更则为不稳定排序。 排序算法中，如果数字相同，则无需变更位置，避免额外的操作。 冒泡排序当两个元素相等时，无需变更位置，也能达到排序效果，所以为稳定排序。