冒泡排序

alt

两两比较依次交换

alt alt

alt

第一趟交换 alt

结果 alt

前面已经确定了的元素不需要对比

alt

算法实现

alt


    public static void main(String[] args) {
        int[] nums={49,38,35,32,65,55,43,90,76};
        int n=nums.length;
//        insertSort(nums,n);
//        shellSort(nums,n);
        bubbleSort(nums,n);
        System.out.println(Arrays.toString(nums));

    }
    //冒泡排序
    public  static  void bubbleSort(int A[],int n){
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-1-i;j++){ //内层扫描的趟数
                if (A[j]>A[j+1]){
                    int temp=A[j];
                    A[j]=A[j+1];
                    A[j+1]=temp;
                }
            }
        }
    }

稳定性分析

alt

空间复杂度O(1)

平均时间复杂度O（n**2）

最坏时间复杂度O(n**2)

冒泡排序是稳定的

冒泡排序是否适用于链表

alt

总结

alt