排序算法-冒泡排序

算法简介

冒泡排序(Bubble Sort)是一种典型的交换排序算法,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。

算法描述

  • 比较相邻的元素。如果第一个比第二个大(小),就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大(小)的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 重复步骤1~3,直到排序完成。

代码实现

    /**
     * 冒泡排序
     *
     * @param array
     */
    private static void bubbleSort(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        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]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

性能分析

最好情况下:正序有序,则只需要比较\(n\)次。故为\(O(n)\)。

最坏情况下:逆序有序,则需要比较 \((n-1)+(n-2)+……+1\),故为\(O(n^2)\)。

当原始序列杂乱无序时,冒泡排序的平均时间复杂度为$O(n^2) $。

因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引),所以其空间复杂度为\(O(1)\)。

冒泡排序在排序过程中,元素两两交换时,相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

排序算法

平均时间复杂度

最好情况

最坏情况

空间复杂度

稳定性

冒泡排序

\(O(n^2)\)

\(O(n)\)

\(O(n^2)\)

\(O(1)\)

稳定

冒泡排序优化(优化外层循环)

若在某一趟排序中未发现位置的交换,则说明待排序的无序区中所有元素均有序,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个标签flag,在每趟排序开始前,先将其置为false。若排序过程中发生了交换,则将其置为true。各趟排序结束时检查flag,若未曾发生过交换则终止算法,不再进行下一趟排序。

    /**
     * 冒泡优化(外层循环优化)
     *
     * @param array
     */
    private static void bubbleSort_2(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        boolean flag = true;//发生了交换就为true, 没发生就为false,第一次判断时必须标志位true
        for (int i = 0; i < array.length - 1; i++) {
            flag = false;//每次开始排序前,都设置flag为未排序过
            for (int j = 0; j < array.length - 1 - i; j++) {//注意数组边界
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true;//表示交换过数据;
                }
            }
            //判断标志位是否为false,如果为false,说明后面的元素已经有序,就直接return
            if (flag == false)
                return;
        }
    }

冒泡排序优化(优化内层循环)

在每趟扫描中,记住最后一次交换发生的位置pos,(该位置之后的相邻记录均已有序)。下一趟排序开始时,\(array[1,pos-1]\)是无序区,\(array[pos,n]\)是有序区。故在进行下一趟排序时只要扫描到pos位置即可。

    /**
     * 冒泡优化(内层循环优化)
     *
     * @param array
     */
    private static void bubbleSort_3(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        boolean flag = true;//发生了交换就为true, 没发生就为false,第一次判断时必须标志位true
        int k = array.length - 1;
        int pos = 0;//pos变量用来标记循环里最后一次交换的位置
        for (int i = 0; i < array.length - 1; i++) {
            flag = false;//每次开始排序前,都设置flag为未排序过
            for (int j = 0; j < k; j++) {//注意数组边界
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true;//表示交换过数据;
                    pos = j;
                }
            }
            k = pos;
            //判断标志位是否为false,如果为false,说明后面的元素已经有序,就直接return
            if (flag == false)
                return;
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

五分钟看懂一个高难度的排序:堆排序

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

11320
来自专栏web前端教室

js数组去重的思路与缓动公式

前端开发的面试中,至少有一类题是必出的,那就是去重。什么叫去重呢?就是把一组字符串中重复出现的,都删除掉。 这种题重要的是解决的思路要正确,思路正确的话其实也很...

24180
来自专栏Python爬虫与算法进阶

说一道排序题

关于Python的sorted排序算法,这篇文章讲的比较详细:python sort函数内部实现原理,说到Python使用的是著名的Timesort算法。

8820
来自专栏程序员互动联盟

【编程基础】C语言循环语句解析

循环语句是一种很重要的结构,这种结构的特点就是在某种条件下,会重复循环执行某一段代码,直到条件不成立为止。这里的条件称为循环条件,重复执行的那段代码称为循环体。...

39050
来自专栏五分钟学算法

每天一算:Evaluate Reverse Polish Notation

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

7810
来自专栏chenjx85的技术专栏

leetcode-58-Length of Last Word

21860
来自专栏python学习之旅

算法笔记(八):复杂度分析(二)

#感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

16420
来自专栏海天一树

AtCoder入门练习题B--题解报告

一、题目 https://practice.contest.atcoder.jp/tasks/practice_2 二、分析 这里有三组测试用例。 第一组N =...

33180
来自专栏积累沉淀

JavaScript面向对象与原型

javaScript有两种开发模式:1.函数式(过程化),2.面向对象(OOP)。面向对象的语言有一个标志,那就是类的概念,而通过类可以创建任意多个具有相同属性...

253100
来自专栏章鱼的慢慢技术路

浅谈main(),int main(),void main(),int main(void)四者之间的区别

13030

扫码关注云+社区

领取腾讯云代金券