vlambda博客
学习文章列表

原理简述

冒泡排序是最简单的排序算法之一，主要是通过不断交换相邻元素，实现排序。

简单例子

对[4,2,6,3,2,1]进行升序排序

• 第一遍（排出最大值）

• 第二遍（排出次大值）

• 第三遍

• 第四遍

• 第五遍每次循环都通过比较相邻的元素，逆序就进行交换，每次都将本次循环内的最大元素交换到最后，通过多次循环，最终变为一个有序的数组。

代码实现Java

public static int[] sort(int[] array){
        //数组长度
        int length = array.length;

        //外层循环
        for (int i=0; i<length-1;i++){
            //内层循环
            for (int j=0; j<length-i-1;j++){
                //如果后面的元素比前面的大，交换
                if (array[j+1]<array[j]){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                }
            }//内层循环 end
            
        }//外层循环 end

        return array;
    }

优化

其实可以发现，如果内层循环没有发生交换，那么数组便已经是有序的，我们便可以退出循环了。我们可以用一个标记，来记录是否发生了交换，进而判断是否还要继续进行排序。

代码实现

    public static int[] sort(int[] array){
        int length = array.length;


        for (int i=0; i<length-1;i++){

            //用来标记是否需要结束循环
            boolean flag = true;

            for (int j=0; j<length-i-1;j++){
                if (array[j+1]<array[j]){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;

                    //发生了交换，不能结束循环
                    flag = false;

                }
            }

            //是否结束循环
            if (flag){
                break;
            }
        }

        return array;
    }

通过这个标记，对于数组[1,2,3,4,5,6]，内循环只需要进行一次，没有发生交换，外部循环就会结束，避免了多余的循环。

算法分析

• 时间复杂度：

最坏情况：O(n^2)
最好情况：O(n)

• 稳定性：冒泡排序是 稳定的排序，在排序过程中，相等的元素的相对位置不会发生变化。

完整代码

public class BubbleSort {



    public static int[] sort(int[] array){
        int length = array.length;


        for (int i=0; i<length-1;i++){

            //用来标记是否需要结束循环
            boolean flag = true;

            for (int j=0; j<length-i-1;j++){
                if (array[j+1]<array[j]){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;

                    //发生了交换，不能结束循环
                    flag = false;

                }
            }

            //是否结束循环
            if (flag){
                break;
            }
        }

        return array;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6};
        int[] sort = sort(arr);

        for (int i : sort) {
            System.out.println(i);
        }

    }
}