Java冒泡排序及优化介绍

什么是冒泡排序

冒泡排序指重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从小到大）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

思路分析

以{5,3,9,7,1}为例要求排序后的数组元素顺序按从小到大排序。依次比较相邻的两个数（蓝色），将比较小的数放在前面，比较大的数放在后面。每一轮排序都能得到参与比较的数的最大值（红色）
第一轮排序
5,3,9,7,1 //如果数大于相邻的数就交换位置
3,5,9,7,1
3,5,9,7,1
3,5,7,9,1
3,5,7,1,9 //第一轮排序的结果
第二轮排序
3,5,7,1,9
3,5,7,1,9
3,5,7,1,9
3,5,1,7,9 //第二轮排序的结果
第三轮排序
3,5,1,7,9
3,5,1,7,9
3,1,5,7,9 //第三轮排序的结果
第四轮排序
3,1,5,7,9
1,3,5,7,9 //第四轮排序的结果

代码实现

public class bubble {
    public static void main(String[] args) {
        int[] array = {5,3,9,7,1};
        bubbleSort(array);
    }
    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] array){
        int temp;
        //一共进行length-1次排序
        for (int i = 0; i < array.length-1; i++) {
            //数组中没有元素或者只有一个元素就无需排序
            if(array==null || array.length < 2 ){
                return;
            }
            //每进行一次排序后参与比较的数量减一
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j]>array[j+1]) {
                    //互换元素位置
                    temp = array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
            System.out.println("第"+(i+1)+"轮排序的结果是"+ Arrays.toString(array));
        }
        return;
    }
}

结果输出

第1轮排序的结果是[3, 5, 7, 1, 9]
第2轮排序的结果是[3, 5, 1, 7, 9]
第3轮排序的结果是[3, 1, 5, 7, 9]
第4轮排序的结果是[1, 3, 5, 7, 9]

Process finished with exit code 0

代码优化

根据上述算法发现对于长度为n的数组需要进行n-1轮排序才能算出最终的结果,但是并非所有数组都需要n-1次才能等要最终的排序结果,比如{1，2，3，5，4}我们发现这个数组只需经过一次排序就能得到结果,那么如何对上面的代码进行优化呢？只需判断一轮排序下来有无出现元素互换位置就可以确定是否完成了排序。如果经过一轮排序元素位置没有发生互换说明排序已经完成

public class bubblePlus {
    public static void main(String[] args) {
        int[] array = {1,2,3,5,4};
        bubboSort(array);
    }
	/**
	*冒泡排序
	*/
    public static void bubboSort(int[] array){
        int temp;
        //判断是否有元素进行交换
        boolean flag = false;
        for (int i = 0; i < array.length-1; i++) {
            if(array==null || array.length < 2 ){
                return;
            }
            //每进行一次排序后参与比较的数量减一
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j]>array[j+1]) {
                    //位置交换就改为true
                    flag = true;
                    temp = array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
            if (!flag){
                //位置没有发生交换说明排序已经完成
                break;
            }else{
                //位置发生改变需要将flag重新置为false以便于下一轮的判断
                System.out.println("第"+(i+1)+"轮排序的结果是"+ Arrays.toString(array));
                flag = false;
            }
        }
        return;
    }
}

优化后的结果输出

第1轮排序的结果是[1, 2, 3, 4, 5]

Process finished with exit code 0

频道导航