我用一张图彻底理解了冒泡排序

432 阅读6分钟

相关文章

通俗易懂讲解【图解】选择排序

1.什么是冒泡排序

本博文介绍最常被提起的排序算法:冒泡排序。冒泡排序是入门排序算法,思路比较常规,但确是最耗时的排序算法,所以听到冒泡排序笑一笑就好了,千万不要拿来装B。

1.1 初识冒泡排序

什么是冒泡排序?

冒泡排序的英文是bubble sort ,它是一种基础的交换排序 。

大家一定都喝过汽水,汽水中常常有许多小小的气泡哗啦哗啦飘到上面 来。这是因为组成小气泡的二氧化碳比水轻,所以小气泡可以一点一点 地向上浮动。

在这里插入图片描述
而冒泡排序之所以叫冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点地向着数组的一侧移动。

具体如何移动呢?让我们先来看一个例子。

在这里插入图片描述
有8个数字组成一个无序数列{5,8,6,3,9,2,1,7},希望按照从小到大的顺序对其进行排序。

按照冒泡排序的思想,我们要把相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧相邻元素时,位置不变 。详细过程如下。

在这里插入图片描述
这样一来,元素9作为数列中最大的元素,就像是汽水里的小气泡一样,“漂”到了最右侧。

这时,冒泡排序的第1轮就结束了。数列最右侧元素9的位置可以认为是一个有序区域,有序区域目前只有1个元素。

在这里插入图片描述
下面,让我们来进行第2轮排序。
在这里插入图片描述
第2轮排序结束后,数列右侧的有序区有了2个元素,顺序如下。
在这里插入图片描述
后续的交换细节,这里就不详细描述了,第3轮到第7轮的状态如下。
在这里插入图片描述

1.2 约定

待排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。

使用辅助函数 less() 和 swap() 来进行比较和交换的操作,使得代码的可读性和可移植性更好。

排序算法的成本模型是比较和交换的次数。

package 算法.排序;/*
作者     :XiangLin
创建时间 :15/05/2020 17:17
文件     :Sort.java
IDE      :IntelliJ IDEA
*/

public abstract class Sort<T extends Comparable<T>>{
    public abstract void sort(T[] nums);

    protected boolean less(T v, T w){
        return v.compareTo(w) < 0;
    }

    protected void swap(T[] a,int i ,int j){
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

1.3 代码

package 算法.排序;/*
作者     :XiangLin
创建时间 :15/05/2020 22:12
文件     :bubblesort.java
IDE      :IntelliJ IDEA
*/

public class bubblesort<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        boolean isSorted = false;
        for (int i = N - 1; i > 0 && !isSorted; i --){
            isSorted = true;
            for (int j = 0; j < i; j++){
                if (less(nums[j+1],nums[j])){
                    isSorted = false;
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Integer[] nums = {5,8,6,3,9,2,1,7};


        System.out.println("原数组:");
        for(int i :nums){
            System.out.print(i+" ");
        }
        System.out.println();
        bubblesort b = new bubblesort();
        b.sort(nums);

        System.out.println("排序后:");
        for(int i :nums){
            System.out.print(i+" ");
        }

    }
}

在这里插入图片描述

1.4 算法分析:

    (1)由此可见:N个数字要排序完成,总共进行N-1趟排序,每i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数 (2)冒泡排序的优点:每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。如上例:第一趟比较之后,排在最后的一个数一定是最大的一个数,第二趟排序的时候,只需要比较除了最后一个数以外的其他的数,同样也能找出一个最大的数排在参与第二趟比较的数后面,第三趟比较的时候,只需要比较除了最后两个数以外的其他的数,以此类推……也就是说,没进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。 (3)时间复杂度   1.如果我们的数据正序,只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值,即:Cmin=n-1;Mmin=0;所以,冒泡排序最好的时间复杂度为O(n)。   2.如果很不幸我们的数据是反序的,则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

在这里插入图片描述
综上所述:冒泡排序总的平均时间复杂度为:O(n2) ,时间复杂度和数据状况无关。

print_r('点个赞吧');
var_dump('点个赞吧');
NSLog(@"点个赞吧!");
System.out.println("点个赞吧!");
console.log("点个赞吧!");
print("点个赞吧!");
printf("点个赞吧!\n");
cout << "点个赞吧!" << endl;
Console.WriteLine("点个赞吧!");
fmt.Println("点个赞吧!");
Response.Write("点个赞吧");
alert(’点个赞吧’)

另外博主收藏这些年来看过或者听过的一些不错的常用的上千本书籍,没准你想找的书就在这里呢,包含了互联网行业大多数书籍和面试经验题目等等。有人工智能系列(常用深度学习框架TensorFlow、pytorch、keras。NLP、机器学习,深度学习等等),大数据系列(Spark,Hadoop,Scala,kafka等),程序员必修系列(C、C++、java、数据结构、linux,设计模式、数据库等等)以下是部分截图

更多文章见本原创微信公众号「五角钱的程序员」,我们一起成长,一起学习。一直纯真着,善良着,温情地热爱生活。关注回复【电子书】即可领取哦

在这里插入图片描述

在这里插入图片描述

所有巧合的是要么是上天注定要么是一个人偷偷的在努力。

有收获?希望老铁们来个三连击,给更多的人看到这篇文章

1、给俺点个赞呗,可以让更多的人看到这篇文章,谢谢各位亲。

2、亲们,关注我的原创微信公众号「五角钱的程序员」,我们一起成长,一起学习。一直纯真着,善良着,温情地热爱生活。关注回复【电子书】有很多资源哦。

给大家推荐一个Github,上面非常非常多的干货:github.com/XiangLinPro…

When I thought I couldn't go on, I forced myself to keep going. My success is based on persistence, not luck.

每当想要放弃时,就强迫自己继续前进。因为我相信,我的成功来源于坚持,而不是幸运。 ​

2020.5.19于城口