资讯专栏INFORMATION COLUMN

数据结构与算法(二):带你读懂冒泡排序(Bubble Sorting)

chuyao / 670人阅读

摘要:经过一次冒泡排序,最终在无序表中找到一个最大值,第一次冒泡结束。也是我们后面要说的冒泡排序的优化。冒泡排序只执行第一层循环,而不会执行第二层循环。因此冒泡排序的时间复杂度是。


1. 基本介绍

冒泡排序(Bubble Sorting),是一种计算机科学领域的较简单的排序算法。它的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始), 依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。故名“冒泡排序”。

2. 冒泡排序理解 2.1 冒泡排序动图


2.2 图解冒泡排序

我们先通过图来简单理解一下一次冒泡的过程

图中可以看出,经过一次冒泡,9这个当前数组中最大的元素飘到了最上面,如果进行N次这样操作,那么数组中所有元素也就到飘到了它本身该在的位置,就像水泡从水中飘上来,所以叫冒泡排序。

具体实现过程:

首先 9 和 2 比较,由于 9 > 2,所以两者交换位置,即从A[0]到A[1]的转变。

然后继续下标为 1 的同下标为 2 的进行比较,由于 9 > 7,所以继续进行位置移动。

直至 A[4],9 和 3 进行比较,继续发生位置交换;

在比较的过程中,找到最大的某一个数,并进行移动。经过一次冒泡排序,最终在无序表中找到一个最大值 9,第一次冒泡结束。

看下整个冒泡过程

从图中我们可以看到,在第三次冒泡的时候,就已经达到了有序状态。因此我们可以做一个标识,当冒泡操作没有进行数据交换时,就可以认为已经达到了有序状态。也是我们后面要说的冒泡排序的优化

3. 冒泡排序代码

通过图片理解完冒泡排序整个过程后,我们开始准备些冒泡排序的算法了。

3.1 冒泡排序过程模拟

在写算法之前,我们先用最笨的办法,把冒泡排序手写一遍,总结下其中的规律在哪?

从上图整个冒泡排序过程,我们可以小结一下:

(1)一共进行数组的大小-1 次大的循环
(2)每一趟排序的次数在逐渐的减少
(3)在冒泡排序中,没有发生一次交换,可以提前结束冒泡排序。这个就是优化

3.2 冒泡排序法算法口诀

口诀

外层循环 0到n-1 //控制比较轮数 n 表示元素的个数

内层循环 0到n-i-1 //控制每一轮比较次数

两两比较做交换

3.3 冒泡排序法算法代码
/**
 * @author: Coder编程
 * @create: 2019-6-18 21:31
 * @description: 冒泡排序
 **/
 
public class BubbleSort {


    public Integer[] bubbleSort(Integer[] arr) {
        //如果只有一个元素就不用排序了
        if (arr.length <= 1) return arr;
 
        for (int i = 0; i < arr.length; ++i) {
            // 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素,这个数组就已经是有序的了
            boolean flag = false;
            for (int j = 0; j < arr.length - i - 1; ++j) {        //此处的 arr.length - i - 1就是每趟排序的减少
                // 数组下标又是从0开始的,i下标后面已经排序的个数就得多减1,总结就是i增多少,j的循环位置减多少
                if (arr[j] > arr[j + 1]) {        //前一位与后一位与前一位比较,如果前一位比后一位要大,那么交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            //没有数据交换,数组已经有序,退出排序
            if (!flag) break;
        }
        return arr;
    }
 
    public static void main(String[] args) {
        Integer arrays[] = {2,9,7,5,3};
        System.out.print("欢迎个人公众号Coder编程:冒泡排序前:");
        Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " "));

        BubbleSort bubbleSort = new BubbleSort();
        Integer[] result = bubbleSort.bubbleSort(arrays);

        System.out.print("
欢迎个人公众号Coder编程:冒泡排序后:");
        Arrays.asList(result).stream().forEach(x -> System.out.print(x + " "));
    }

输出结果:

4. 冒泡排序优化

上面的代码已经进行过优化,加了排序中,没有发生一次交换,提前结束冒泡排序的标识flag

这里推荐另外一种优化方式:鸡尾酒排序,也叫双向冒泡排序

public static Integer[] sort(Integer[] arr){
    //依次将最大的数放置到数组末尾,将第二大的数放到倒数第二位...
    boolean changed;
    for(int i = 0;i < arr.length/2;i++){
        changed = false;
        //从前往后,比较相邻两个数,把大的放在后边.之前已放置成功的可以不再参与比较
        for(int j = i;j < arr.length-1-i;j++){

            if(arr[j]>arr[j+1]) {
                swap(arr,j,j+1);
                changed =true;
            }
        }
        if(!changed){
            break;
        }
        for(int j = arr.length-1-i; j > i; j--){

            if(arr[j]
5. 冒泡排序性能分析

对于时间复杂度与空间复杂度概念不太了解的朋友可以看我写的上一篇文章: 数据结构与算法(一):带你了解时间复杂度和空间复杂度到底是什么?

5.1 最劣的情况 O(n^2)

计算最糟糕情况,就是全部逆序情况。时间复杂度为O(n^2)

比较次数移动次数分别为n(n-1)/23n(n-1)/2

我们以比较次数进行理解

冒泡排序一共要进行(n-1)次循环,每一次循环都要进行当前n-1次比较。所以一共的比较次数是:

(n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2;

因此冒泡排序的时间复杂度是 O(n2)。

移动次数很好理解。会发生3次交换,因此常量系数为3。

5.1 最优的情况 O(n)

计算优情况时,也就是全部是顺序的情况下。冒泡排序只执行第一层for循环,而不会执行第二层for循环。

因此冒泡排序的时间复杂度是 O(n)。

6. 冒泡排序扩展阅读 6.1 C语言版
void bubble ( int arr[], int n)
{
    int i;
    int temp;
    for (i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
}

void bubbleSort ( int arr[], int n)
{
    int i;
    for (i = n; i >= 1; i--) {
        bubble(arr, i);
    }
}
6.2 Python版
def sort_myarr():
    myarr=[2,9,7,5,3]
    lenth=len(myarr)
    for i in range(lenth):
        for j in range(lenth-i-1):
            if myarr[j]>myarr[j+1]:
                temp=myarr[j]
                myarr[j]=myarr[j+1]
                myarr[j + 1]=temp

    print(myarr)
6.3 JS版
var examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){
    for(i=0;iarr[j+1]){
                var temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
}
sortarr(examplearr);
console.log(examplearr);
6. 冒泡排序总结

优点: 比较简单,空间复杂度较低,是稳定的。
缺点: 时间复杂度太高,效率不好。

其他可看上面的小结算法口诀

参考文章

https://cloud.tencent.com/dev...

http://www.pianshen.com/artic...

https://blog.csdn.net/Hydra_s...

文末
欢迎关注个人微信公众号:Coder编程
获取最新原创技术文章和免费学习资料,更有大量精品思维导图、面试资料、PMP备考资料等你来领,方便你随时随地学习技术知识!
新建了一下qq群:315211365,欢迎大家进群交流一起学习。谢谢了!也可以介绍给身边有需要的朋友。

文章收录至
Github: https://github.com/CoderMerli...
Gitee: https://gitee.com/573059382/c...


文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/77848.html

相关文章

  • 数据结构算法(三):带你读懂选择排序(Selection sort)

    摘要:基本介绍选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。而移动次数与序列的初始排序有关。空间复杂度简单选择排序需要占用个临时空间,在交换数值时使用。 showImg(https://img-blog.csdnimg.cn/20190509221741422.gif); showImg(https://segmentfault....

    Kaede 评论0 收藏0
  • JavaScript 排序算法图解(JavaScript sorting algorithms)

    摘要:基础构造函数以下几种排序算法做为方法放在构造函数里。代码图解选择排序选择排序算法是一种原址比较排序算法。它的性能通常比其他的复杂度为的排序算法要好。代码划分过程图解排序没有定义用哪个排序算法,所以浏览器厂商可以自行去实现算法。 基础构造函数 以下几种排序算法做为方法放在构造函数里。 function ArrayList () { var array = []; // 交换位置...

    h9911 评论0 收藏0
  • 常见排序算法及其实现(Binary,Insert、Select、Quick、Bubble.etc.S

    摘要:常见排序算法及其实现说明如果有幸能看到本文中的代码是参考编程思想某培训机构。若两个记录和的关键字相等,但排序后的先后次序保持不变,则称为这种排序算法是稳定的。 常见排序算法及其实现 说明 如果有幸能看到 1、本文中的代码是参考《Java编程思想》、某培训机构。 2、文中的代码放Github了,有兴趣的可以看看,点个star鼓励下我。 3、代码在Sublime中敲的,坑爹的GBK,注释...

    187J3X1 评论0 收藏0
  • 冒泡排序

    摘要:概述冒泡排序是一种简单的排序算法。走访数列的工作是重复地进行直到数列已经排序完成。简单点说,就是冒泡排序是將比較大的數字沉在数组的后面可以理解为下面,较小的浮在前面上面。 概述 冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢浮到...

    13651657101 评论0 收藏0
  • JavaScript 版各大排序算法

    摘要:推荐一下,,这里还有个可视化的排序博客,各大排序算法的实现都栩栩如生。堆排序堆排序是指利用堆这种数据结构所设计的一种排序算法。共勉参考维基百科排序搜索聊一聊排序算法秒杀种排序算法版排序图解排序算法实现欢迎来我的博客交流 最近看到了很多公司都在准备明年的实习校招,虽然离三月份还有一段时间,感觉已经可以准备了。在网上看了一些排序算法和数组去重操作,感觉都写的很好,心血来潮,也来写一写。 s...

    FrozenMap 评论0 收藏0

发表评论

0条评论

chuyao

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<