排序之冒泡排序

前言

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中都有详细讲解,而我写这些博客只是记录自己学习过程,加入了一些自己的理解,同时也希望给别人提供帮助。

无论你学习哪种编程语言,在学到循环和数组时,通常都会介绍一种排序算法来作为例子,而这个算法一般就是冒泡排序。并不是它的名称很好听,而是说这个算法的思路最简单,最容易理解。因此,哪怕大家可能都已经学过冒泡排序了,我们还是从这个算法开始我们的排序之旅。

基本思想

   两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。冒泡的实现在细节上可以很多种变化,我们就最简单的一种冒泡实现代码,来讲解冒泡排序的思想。

代码实现

 1     /**
 2      * 冒泡排序
 3      * 大的往下沉,小的往上冒
 4      * @param arr
 5      */
 6     public void buttleSort(int[] arr){
 7         int len = arr.length;
 8         // i表示第几轮比较(9个数字的话只需要比较8次)
 9         for(int i=1; i<len; i++){
10             // 大的往下沉,小的往上冒
11             for(int j=len-1; j>=i; j--){
12                 if(arr[j-1] > arr[j]){        // 若前者大于后者
13                     swap(arr,j-1,j);        // 交换arr[j-1]与arr[j]
14                 }
15             }
16         }
17     }

执行过程模拟

假设我们要排序的序列依然是{5,3,7,9,1,6,4,8,2},当i=1时,变量j由8反向循环到1,逐个比较,将较小值交换前面,直到最后找到最小值放置在了第1的位置。如图5-1,当i=1,j=8时,我们发 现8>2,因此交换了它们的位置,j=7时,4>2,所以交换……直到j=5时,因为1<2,所在不交换。j=1时,5>1,交 换,最终得到最小值1放置第一的位置。事实上,在不断循环的过程中,除了将关键字1放到第一的位置,我们还将关键字2从第九位置提到到了第六的位置。图中较小的数字如同气泡般慢慢浮到上面,因此就将此算法命名为冒泡算法。

  当i=2时,变量j由8反向循环到2,逐个比较,在将关键字2交换到第二位置的同时,也将关键字4有所提升。

  后面的过程一样的,这里就不在赘述了。

总结

  冒泡排序是比较好理解的,应该是没什么难点,但是上述的代码是可以改善的。试想一下,如果我们待排序的序列是{2,1,3,4,5,6,7,8,9},也就是说,除了第一和第二的关键字需要交换外,别的都已经是正常的顺序。当 i=1时,交换了2和1,此时序列已经有序,但是算法仍然不依不饶的将i=2到9,以及每个循环中的j循环都执行了一遍,尽管并没有交换数据,但是之后的大量比较还是大大的多余了。那么如何进行改善,就当是给大家的思考题了

  对改善实在是没有办法的,可以点这里,讲到了冒泡排序的优化。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之数值的整数次方(九度OJ1514)

题目描述: 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 输入: 输入可能包含多个测试样例。 ...

22570
来自专栏机器学习原理

python函数基础字符串操作numpy 和list互相转换

list 转 numpy np.array(a) ndarray 转 list a.tolist() 写入文件必须是字符

51010
来自专栏用户画像

C语言测试题

2. 假设已指定i为整型变量,f为float变量,d为double型变量,e为long型,有下面式子:

22650
来自专栏猿人谷

三十分钟掌握STL

这是本小人书。原名是《using stl》,不知道是谁写的。不过我倒觉得很有趣,所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟...

27880
来自专栏九彩拼盘的叨叨叨

学习纲要:JavaScript 基础语法

12330
来自专栏Petrichor的专栏

tensorflow: Shapes and Shaping 探究

10810
来自专栏yl 成长笔记

UML 类图基础

定义:两个类之间的强依赖关系, 可以为单向,亦可为双向。常见表现形式 为 A 类中有 B 类型的成员变量。

12140
来自专栏python成长之路

集合常用操作

17640
来自专栏Fish

CUDA PTX ISA阅读笔记(一)

不知道这是个啥的看这里:Parallel Thread Execution ISA Version 5.0. 简要来说,PTX就是.cu代码编译出来的一种东西...

39650
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》 附录A NumPy高级应用A.1 ndarray对象的内部机理A.2 高级数组操作A.3 广播A.4 ufunc高级应用A.5 结构化和记录式数组A.6 更多

在这篇附录中,我会深入NumPy库的数组计算。这会包括ndarray更内部的细节,和更高级的数组操作和算法。 这章包括了一些杂乱的章节,不需要仔细研究。 A.1...

73660

扫码关注云+社区

领取腾讯云代金券