Java数据结构与算法(4) -冒泡排序

前言

最近编程状态很自由,我挺喜欢这种感觉。不过还是要给自己制定一个计划,每天学习一小节《Java数据结构与算法》和看一小节刘宇波老师的《数据结构与算法》视频,还有就是学习Spring Boot项目课程。然后每天晚上的时候,写一篇简书总结自己一天回顾的知识。


从简单的冒泡排序开始

冒泡排序算法运行起来十分慢,但在概念上它是排序算法中最简单的,因此冒泡排序算法在开始研究排序技术时是一个非常好的算法。


什么是冒泡排序?

对几个无序的数字进行排序,最常用的方法是所谓的冒泡排序。算法思想是每次比较2个相邻的数字,将小的放在前面,将较大的放在后面,这样就可以将这些数中最大的找出来放在到最后。然后再比较剩下的数字,再在这些数字中找出最大的,直到所有的数字按照从小到大的顺序进行排序。

提炼思想

  • 在算法执行的时候,最大的数据项总是冒泡到数据的顶端。
  • 假如有N个数字需要进行排序,在对所有的数字进行了第一趟排序之后,进行了N - 1次比较,并且按照数字之间的初始位置,进行了最少0次,最多N - 1次交换,数组最末端的数据项就此排定。
  • 我们进行第二趟排序的时候,再一次地从左到右,两两比较,并且在适当的时候交换数字之间的顺序,这一次只需要比较到右边第二个数字(位置 N - 2)就行了,因为最大的数字已经到了最后位置,既N - 1号位置。

开始练手

  • 只有把思路理清楚了,才能开始写代码。
public class BubbleSortDemo {
    public static int[] a = { 2, 4, 6, 8, 3, 6, 9, 12 };

    public static void main(String[] args) {
        sort();
        display();
    }

    public static void sort() {
        int count = a.length;

        for (int i = 0; i < count - 1; i++) {
            for (int k = 0; k < count - 1 - i; k++) {
                if (a[k] > a[k + 1]) {
                    swap(k, k + 1);
                }
            }
        }
    }

    public static void swap(int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    public static void display() {
        int count = a.length;

        for (int i = 0; i < count; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
}
  • 运行程序,看控制台输出结果。

image.png


性能优化

我们使用的是一个独立的swap()方法来执行交换操作的。它只是交换数组中的两个数据项的值,使用一个临时变量来存储第一个数据项的值,然后把第二项的值赋给第一项,之后再让第二项的值等于临时变量。实际上,使用一个独立的swap()方法不一定好,因为方法调用会增加一些额外的开销,如果写自己使用的排序程序,最好将交换操作这段代码直接放到程序中,这样可以提高一些速度。


冒泡排序的效率

  • 我们发现在第一趟排序时进行了9次比较,第二趟排序时进行了8次比较,以此类推,直到最后一趟进行了一次比较。那么10个数据项,一共就进行了9 + 8 + ... + 1 = 45次,也就是N * (N - 1)/ 2。如果初始数据项时逆序的时候,我们每次比较都需要交换。可以知道冒泡排序运行需要O(N^2)时间级别,这样速度是很慢的。
  • 只要看到了一个循环嵌套在另一个循环中,就可以怀疑这个算法的运行时间为O(N^2)级。

尾言

勿以善小而不为。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开源优测

Python3希尔排序

希尔排序 概述 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminshing Increment Sort),是直接插入排序算...

35510
来自专栏JavaEE

Java面试题-01前言:面试题:总结:

1895
来自专栏C语言C++游戏编程

世界最强的编程语言:C语言

char:字符型,用来存储小范围的整数(-128~127)和字符(所有的ASCII字符,128个),一个字节。

1522
来自专栏带你撸出一手好代码

正则表达式「^」符号的正确理解方式

「^」这个符号在正则表达式的中的应用相信是所有程序员都掌握的, 因为它是正则表达式中最基础最常用的知识点。 它在正则表达式中表示两种不同的意义 01 表示匹配一...

2873
来自专栏移动端开发

swift 可选类型笔记

       晚上十一点半了,看书累了,原本想睡了的,想了想,还是把刚看的总结一下,把这篇笔记写了吧。广州下雨,真特么的冷。。好了,废话不说了,说正题说说Swi...

19610
来自专栏我的博客

冒泡排序

原理: 1、比较相邻的元素。如果第一个比第二个大(小),就交换他们两个。 2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元...

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

学点算法之字符串的乱序检查

问题 字符串的乱序检查。 一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列,例如,’heart’ 和 ‘earth’ 就是乱序字符串。’py...

4098
来自专栏liulun

Nim教程【六】

目前看来这是国内第一个关于Nim的系列教程 先说废话 Rust1.0已经发布了, 国内有一个人为这个事情写了一篇非常长的博客, 这篇文章我前几天草草的看了...

2446
来自专栏算法channel

Python:lambda表达式的两种应用场景

python书写简单,功能强大, 迅速发展成为 AI ,深度学习的主要语言。介绍Python中的lambda表达式,注意到,它只是一个表达式,不是语句啊。

1331
来自专栏老马说编程

(19) 接口的本质 / 计算机程序的思维逻辑

数据类型的局限 之前我们一直在说,程序主要就是数据以及对数据的操作,而为了方便操作数据,高级语言引入了数据类型的概念,Java定义了八种基本数据类型,而类相当...

21110

扫码关注云+社区

领取腾讯云代金券