图解冒泡排序

1. 图示过程

冒泡排序图示

2. 文字叙述过程

对于一组包含n个数据的记录,冒泡排序在最坏的情况下需要进行n-1趟排序

  • 第1趟:依次比较0和1、1和2、2和3...(n-2)和(n-1)索引的元素,如果发现第1个数据大于第2个数据,交换他们,经过第1趟排序,最大的元素排到了最后
  • 第2趟:依次比较0和1、1和2、2和3...(n-3)和(n-3)索引的元素,如果发现第1个数据大于第2个数据,交换他们,经过第2趟排序,第二大的元素排到了倒数第二个位置
  • ...
  • 第n-1趟:比较0和1索引的元素,如果发现第1个数据大于第2个数据,交换他们,经过第n-1趟排序,第二小的元素排到了第二个位置

3. Java代码实现

public static void bubbleSort(int[] nums) {
    int temp;
    for(int i = 1; i < nums.length; i++) {
        for(int j = 0; j < nums.length - i; j++) {
            if(nums[j] > nums[j+1]) {
                temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }
}

4. 复杂度

  • 时间复杂度:O(n²)
  • 空间复杂度:O(1),只需要一个附加程序单元用于交换
  • 稳定性:不稳定 冒泡排序是不稳定的排序算法,最好情况下(初始数组本来就有序),算法执行一趟冒泡即可,做 n-1 次比较,0次交换即可,最坏情况下(初始数组完全逆序),算法需要执行 n-1 趟冒泡,比较总次数为 n * (n-1) / 2,交换总次数为 n * (n-1) / 2

5. 优化

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

public static void bubbleSort(int[] nums) {
    int temp;
    for(int i = 1; i < nums.length; i++) {
        boolean flag = true;
        for(int j = 0; j < nums.length - i; j++) {
            if(nums[j] > nums[j+1]) {
                temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
                flag = false;
            }
        }
        if(flag) {
            // 如果某趟没有交换,说明数组已经有序
            break;
        }
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python3

python random模块

随机输出一个0~4的数字和range()输出的数字,去比较。猜对了,就是字母,否则是数字

8620
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

30790
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

16910
来自专栏Jack-Cui

Day3、Python

题目 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1、程序分析     根据题意可知,需要用到字符串的操作方法。本题中要用到的三...

18200
来自专栏owent

最长单调子序列 复杂度nlog(n)

7910
来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

10610
来自专栏和蔼的张星的图像处理专栏

488. 快乐数

一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可...

16530
来自专栏数据结构与算法

P3809 【模版】后缀排序

题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

26980
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

30870
来自专栏wym

18年暑假多校赛第一场 1004

题目地址http://acm.hdu.edu.cn/showproblem.php?pid=6301

8420

扫码关注云+社区

领取腾讯云代金券