Java实现冒泡算法及优化冒泡算法

Java实现冒泡算法及优化冒泡算法基本思想冒泡排序(BubbleSort)通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序(前后大小与要求的顺序不一致)则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。代码实现publicclassBubbleSort{/***按照从小到达的顺序进行排序*@paramarray要进行排序的数组*/publicstaticvoidbubbleSort(int[]ar

基本思想
冒泡排序(Bubble Sort)通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序(前后大小与要求的顺序不一致)则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。

代码实现

public class BubbleSort { 
   

    /** * 按照从小到达的顺序进行排序 * @param array 要进行排序的数组 */
    public static void bubbleSort(int[] array){ 
   
        int temp = 0;//用于前后元素交换时使用

        //数组有n个元素,排序只需n-1次就能完成
        for (int i = 0; i <array.length-1 ; i++) { 
   
            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;
                }
            }
        }
    }
}

代码解释:
在这里插入图片描述
测试数组:int[] array = {23,9,-2,-1,8,99,100,91};
执行结果:
在这里插入图片描述
算法优化
可以从上述的每一趟的输出结果可以看出,在第二次排序完成后整个数组就已经按照从小到大的顺序排列了,后面的几次循环只是在执行if语句,而实际上并没有进行排序。浪费了时间和空间
优化:

int temp = 0;//用于前后元素交换时使用
boolean isChanged = false;//标识变量,记录数组是否提前完成了排序

//数组有n个元素,排序只需n-1次就能完成
for (int i = 0; i <array.length-1 ; i++) { 
   
    for (int j = 0; j <array.length-1-i ; j++) { 
   
        if (array[j]>array[j+1]){ 
   
            isChanged  =true;//证明元素交换过,即数组还未完全有序
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
        }
    }
    if (!isChanged){ 
   
        break;//左右元素未交换,说明数组已完成排序,结束排序循环
    }
    System.out.printf("第%d次排序结果",i+1);
    System.out.println(Arrays.toString(array));
    isChanged = false;//重置,用于下次判断,这个重置非常重要
}

执行结果:
在这里插入图片描述
可以看出来for循环只执行了两次就结束并完成了数组的排序

今天的文章Java实现冒泡算法及优化冒泡算法分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/24958.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注