搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > JAVA首席架构师 > 冒泡排序算法(JAVA)

冒泡排序算法(JAVA)

JAVA首席架构师 2019-10-10
举报

微信公众号:Java野生程序猿
如有问题或建议,请公众号留言

它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。


这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。


原理:比较两个相邻的元素,将值大的元素交换至右端。


依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。

  • 第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。

  • 比较第2和第3个数,将小数 放在前面,大数放在后面。

  • 如此继续,知道比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成

  • 在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的。

  • 在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。

  • 依次类推,每一趟比较次数减少依次




举例说明:要排序数组:int[] arr={6,3,8,2,9,1};   


第一趟排序:


    第一次:6和3比较,6大于3,交换位置:  3  6  8  2  9  1


    第二次:6和8比较,6小于8,不交换位置:3  6  8  2  9  1


    第三次:8和2比较,8大于2,交换位置:  3  6  2  8  9  1


    第四次:8和9比较,8小于9,不交换位置:3  6  2  8  9  1


    第五次:9和1比较:9大于1,交换位置:  3  6  2  8  1  9


    第一趟总共进行了5次比较, 结果为:      3  6  2  8  1  9




第二趟排序:  

             第一次:3和6比较,3小于6,不交换位置:3  6  2  8  1  9


    第二次:6和2比较,6大于2,交换位置:  3  2  6  8  1  9


    第三次:6和8比较,6大于8,不交换位置:3  2  6  8  1  9


    第四次:8和1比较,8大于1,交换位置:  3  2  6  1  8  9


    第二趟总共进行了4次比较, 结果为:      3  2  6  1  8  9




第三趟排序:

  

          第一次:3和2比较,3大于2,交换位置:  2  3  6  1  8  9


    第二次:3和6比较,3小于6,不交换位置:2  3  6  1  8  9


    第三次:6和1比较,6大于1,交换位置:  2  3  1  6  8  9


    第三趟总共进行了3次比较, 结果为:         2  3  1  6  8  9





第四趟排序:


    第一次:2和3比较,2小于3,不交换位置:2  3  1  6  8  9


    第二次:3和1比较,3大于1,交换位置:  2  1  3  6  8  9


    第四趟总共进行了2次比较, 结果为:        2  1  3  6  8  9




第五趟排序:

  

          第一次:2和1比较,2大于1,交换位置:  1  2  3  6  8  9


    第五趟总共进行了1次比较, 结果为:  1  2  3  6  8  9




最终结果:1  2  3  6  8  9




冒泡排序的优点:每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。如上例:第一趟比较之后,排在最后的一个数一定是最大的一个数,第二趟排序的时候,只需要比较除了最后一个数以外的其他的数,同样也能找出一个最大的数排在参与第二趟比较的数后面,第三趟比较的时候,只需要比较除了最后两个数以外的其他的数,以此类推……也就是说,没进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。


时间复杂度



冒泡排序总的平均时间复杂度为:O(n2) 


代码实现:


import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {46233532056};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        //记录最后一次交换的位置
        int lastExchangeIndex = 0;
        //无序数列的边界,每次比较只需要比到这里为止
        int sortBorder = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            boolean isSorted = true;
            //无序数列的边界,每次比较只需要比到这里为止
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    //有元素交换,所以不是有序,标记变为false
                    isSorted = false;
                    //把无序数列的边界更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            if (isSorted) {
                break;
            }

        }
    }

}



如果您喜欢,分享一下让更多的人学习

请点击标题下方的“Java野生程序猿”添加关注

或者长按下方的二维码添加关注


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《冒泡排序算法(JAVA)》的版权归原作者「JAVA首席架构师」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注JAVA首席架构师微信公众号

JAVA首席架构师微信公众号:The-Retired-King

JAVA首席架构师

手机扫描上方二维码即可关注JAVA首席架构师微信公众号

JAVA首席架构师最新文章

精品公众号随机推荐

举报