轻松读懂数据结构系列:早操排队图解冒泡排序

一、说在前面

一直想写一些简单易懂的文章,因为平时看的很多的书籍或者文章都是看着很难受的感觉,当然,这并不是说书籍写的不好,只是说对于一些没有太多基础或者基础不是很好的来说,相对来说还是比较难以理解的。

这个系列主要是写一些简单易懂的数据结构与算法的文章,同时也是帮助自己再理解理解这方面的知识。

作为数据结构与算法的开篇,还是以排序算法作为第一部分的内容,需要注意的是,这一系列的文章并不是涉及到很多理论性质的知识,因为前面说了,主要还是希望文章是简单易懂的,希望能达到读故事的感觉。如果需要去学习理论性质的知识,可以去查看相关的数据结构与算法的书籍。

二、冒泡排序算法

作为这一系列的第一部分,主要讲解排序算法。从小到大,我们至少前20年的时间都是在学校度过了,校园生活在我看来是十分的美好的,以至于现在我都还在校园里面生活。在我们读书的阶段,是不是经常会碰到排队的时候,因为大家都熟悉这一场景,所以,我们就一排队来讲解排序算法

冒泡算法应该是我们最熟悉不过的算法了,也是我们最熟悉不过的排队了,既然熟悉不过,那么我们今天就来排个冒泡排序的队列吧。

今天早上,老师叫我们去操场上做早操,做早操之前呢,需要排队,排队都有一个排法,不是吗?那么,老师今天就要求我们按照身高由低到高依次排好

于是,我们早上很快就一起到了操场上,总共有5个人到了操场,刚刚去的时候,队列肯定是散的对吧,这时候的队列是下面这样子的:第0个位置站的小明,第1个位置站的小海,第2个位置站的小刘,第3个位置站的小李,第5个位置站的小爱。

于是老师(假设老师是一个程序员哈,皮一下)要求我们按照冒泡排序的方法排好队:挨个的比较身高,如果比下一个位置上的同学高,就换一下位置

好了,同学们听到老师的指示之后呢,同学们就开始动身了。

第0个位置上的小明同学和第1个位置上的小海同学相互比了一下身高,发现第1个位置上的小海同学(1.80m)比第0个位置上的小海同学(1.60m)高,于是就保持不动,所以第一次排队后,队列还是保持不变的。

接下来,第1个位置上的小海同学还想和第2个位置上的小刘同学比一下身高,发现第1个位置上的小海同学比第2个位置上的小刘同学高,所以,他们互换一下位置。

于是,队列成了下面的样子,小海和小刘换了一下位置

之后,第2个位置上的小海同学,又和第3个位置上的小李同学比了一下身高,发现,第2个位置上的小海同学还是比第3个位置上的小李同学高,所以他们还是需要交换一下位置的。

这时候,队列变成了下面的样子,小海和小李互换

接下来第3个位置上的小海同学和第4个位置上的小爱同学进行了身高的比较,发现第3个位置上的小海同学还是比第4个位置上的小爱同学高,所以又需要换一下。

交换后,变成了这样子:

结果我们发现,通过这种排序方法,最高的小海从第2个位置上跑到了最后一个位置

好了,现在最高的小海的位置已经确定了,我们就不管他了,我们又从第0个位置上的同学开始,第0个位置的小明同学和第1个位置的小刘同学比较身高,发现小明的身高比小刘的矮,所以队列维持不变。


接下来,第1个位置上的小刘和第2个位置上的小李比较,发现,小刘比小李高,所以需要交换位置


交换后,变成了下面的队列

然后,第2个位置上的小刘和相邻的第3个位置上的小爱比较身高,发现小爱比小刘高,所以不交换位置

最后一个位置的小海因为第一轮已经知道他最高了,所以不与他比较了,因此,这轮排完之后,我们发现,整个序列已经是有序的了,我们看一下队列的变化。

从这排队的过程中,我们是不是发现了冒泡排序的思想

第一遍,第一个位置上的同学开始,挨个的比较身高,如果第0个位置的同学比第1个位置的同学高,就交换位置,否则,不换位置,然后,第1个位置与第2个位置的同学比一下身高,如果第1个位置的同学高比第2个位置的同学高,交换位置,否则不换,以此类推,最高的同学将会到最后一个位置上。

第二遍,还是从第一个位置上的同学开始,第1个同学和第2个同学比较,如果第一个同学比第二个同学高,交换位置,否则不变,然后,第2个位置上的同学和第3个位置的同学比较,如果第2个位置的同学高,则交换位置,否则不换。这一遍,因为第一遍已经找出来最高的同学在最后一个位置,所以最后一个位置不用比较了。

直到队列全部排好为止。

到这里,我想你应该明白了冒泡排序的思想了。

接下来,我们看一下代码的实现(这里我们使用Java代码实现)。


public static void bubbleSort(int[] arr) {
        //如果数组为空,或者元素为1,直接返回。
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int e = 0; e < arr.length - 1; e++) {//每次最大元素就像气泡一样"浮"到数组的最后
            for (int i = 0; i < n-1-e; i++) {//n-1-e:-1是因为元素从0下表开始,-e是因为可以减去已排到最后的几个元素,可以减少比较次数。
                if (arr[i] > arr[i + 1]) {//如果大于下一个位置
                    swap(arr, i, i + 1);//交换位置
                }
            }
        }
    }

    /**
     * 交换元素位置
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
性能分析

最差时间复杂度:O(n^2)
最优时间复杂度:如果已经是有序的,可以把最优时间复杂度降低到O(n)
平均时间复杂度:O(n^2)
所需辅助空间:O(1)
稳定性:稳定
稳定性说明:排序稳定不稳定,就是看每次排序的过程中,是否会改变整个序列的位置。

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号 好好学java,获取优质学习资源。


 上一篇
Dubbo 一篇文章就够了:Dubbo遇到初恋 Dubbo 一篇文章就够了:Dubbo遇到初恋
一 为什么需要 dubbo很多时候,其实我们使用这个技术的时候,可能都是因为项目需要,所以,我们就用了,但是,至于为什么我们需要用到这个技术,可能自身并不是很了解的,但是,其实了解技术的来由及背景知识,对于理解一项技术还是有帮助的,那么,d
下一篇 
当初的年味还在吗? 当初的年味还在吗?
365天,一年又过去了,真的是时光飞逝,想想去年的种种都还历历在目呢,但就是这样还没缓过神来,又到了一年最重要的节日了,在这里,小海祝小伙伴们新春快乐,新的一年事事如意,都能实现自己的目标和愿望,另外,家人都健健康康的! 回到家已经有几天
  目录