面试 9:Java 玩转冒泡排序
面试 9:用 Java 实现冒泡排序
南尘的朋友们,新的一周好,原本打算继续讲链表考点算法的,这里姑且是卡一段。虽然在我们 Android 开发中,很少涉及到排序算法,因为基本官方都帮我们封装好了,但排序算法也是非常重要的,在面试中 归并排序 和 快速排序 一直为高频考点,但在学习它们之前,我们必须得先把三大基础算法学会,毕竟层层递进,方得始终嘛。
冒泡排序
冒泡排序恐怕是我们计算机专业课程上以第一个接触到的排序算法,也算是一种入门级的排序算法。它的基本思想是:两两比较相邻记录的关键字,如何反序则交换,直到没有反序的记录为止。
冒泡排序算法原理:
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
一次比较过程如图所示:
我们通常容易想到最简单的实现代码:
public class Test09 { private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void printArr(int[] arr) { for (int anArr : arr) { System.out.print(anArr + " "); } } private static void bubbleSort(int[] arr) { if (arr == null) return; for (int i = 0; i < arr.length - 1; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) swap(arr, i, j); } } } public static void main(String[] args) { int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5}; bubbleSort(arr); printArr(arr); } }
严格地讲,上面的算法并不是冒泡排序,因为 它完全不符合两两相邻比较。它更应该是最最简单的就交换排序而已。它的思路是让每一个关键字,都和它后面的每一个关键字比较,如果大则交换,这样第一位置的关键字在一次循环后一定变成最小值。
我们不妨来看看正宗的冒泡排序算法。
public class Test09 { private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void printArr(int[] arr) { for (int anArr : arr) { System.out.print(anArr + " "); } } private static void bubbleSort(int[] arr) { if (arr == null) return; for (int i = 0; i < arr.length - 1; i++) { for (int j = 1; j < arr.length - i; j++) { if (arr[j - 1] > arr[j]) { swap(arr, j - 1, j); } } } } public static void main(String[] args) { int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5}; bubbleSort(arr); printArr(arr); } }
上述代码是否完美了呢?答案是否定的,我们假设待排序的序列是 {2,1,3,4,5,6,7,8,9},也就是说,除了第一和第二个关键字需要交换外,别的都应该是正常的顺序,当 i = 1 时,交换了 2 和 1 的位置,此时已经有序,但是算法依然不依不挠地将 i = 2 到 9 以及每一个内循环都执行了一遍,尽管没有交换数据,但之后的大量比较还是大大的多余了。所以我们完全可以设置一个标记位 isSort
,当我们比较一次后都没有交换,则代表数组已经有序了,此时直接退出循环即可。
既然思路已经确定,那代码自然是很信手拈来了。
public class Test09 { private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void printArr(int[] arr) { for (int anArr : arr) { System.out.print(anArr + " "); } } private static void bubbleSort(int[] arr) { if (arr == null) return; // 定义一个标记 isSort,当其值为 true 的时候代表已经有序。 boolean isSort; for (int i = 0; i < arr.length - 1; i++) { isSort = true; for (int j = 1; j < arr.length - i; j++) { if (arr[j - 1] > arr[j]) { swap(arr, j - 1, j); isSort = false; } } if (isSort) break; } } public static void main(String[] args) { int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5}; bubbleSort(arr); printArr(arr); } }
Perfect 的代码,但冒泡排序在数组长度较大的时候,效率真的很低下,所以在实际生产中,我们也很少使用这种算法。
冒泡排序时间空间复杂度及算法稳定性分析
对于长度为 n 的数组,冒泡排序需要经过 n(n-1)/2 次比较,最坏的情况下,即数组本身是倒序的情况下,需要经过 n(n-1)/2 次交换,所以其
冒泡排序的算法时间平均复杂度为 O(n²)。空间复杂度为 O(1)。
可以想象一下:如果两个相邻的元素相等是不会进行交换操作的,也就是两个相等元素的先后顺序是不会改变的。如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个元素相邻起来,最终也不会交换它俩的位置,所以相同元素经过排序后顺序并没有改变。
所以冒泡排序是一种稳定排序算法。所以冒泡排序是稳定排序。这也正是算法稳定性的定义:
排序算法的稳定性:通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。
冒泡排序总结:
- 冒泡排序的算法时间平均复杂度为 O(n²)。
- 空间复杂度为 O(1)。
- 冒泡排序为稳定排序。
考虑到不少读者说每天代码量太多的问题,我们今天就只讲冒泡排序的 Java 实现,我们明天将带来三大简单排序的另外两种,选择排序 和 插入排序。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
flag在index里(详解)——Bugku
刚刚做了bugku的题目,现在整理一下 写出解题思路,希望能够帮助到那些需要帮助的人 所有的wp都是以一题一篇的形式写出 主要是为了能够让读者更好的阅读以及查找, 希望你们不要责怪!!共勉!!! Challenge 1152 Solves flag在index里 80 http://120.24.86.145:8005/post/ 解题思路: 首先打开这道题,页面只给你click me? no 点击进去显示test5 第一步,查看源代码,无果 第二步bp,无果 结合到题目,flag在index里,大胆尝试http://120.24.86.145:8005/post/index.php,可惜和之前一样 注意到了传值为http://120.24.86.145:8005/post/index.php?file=show.php file这个变量应该是关键,可惜无果 参考到别的博主的wp: file传值为: php://filter/read=convert.base64-encode/resource=index.php 就会得到: base64解密下就得到flag了 可能很...
- 下一篇
C#——Nhibernate探索
C#—Nhibernate探索 本篇文章,让我们一起来探索Nhibernate。 首先我们去搜索Nhibernate下载地址,如下链接所示。 该版本可能是最新版,我下载的4.0.4.GA。其中GA意思我没搞清楚。不过应该不重要。 https://sourceforge.net/projects/nhibernate/ 分析文件内容 下载完成后,解压缩,我们看到文件夹内容如下图所示。 我们可以分析得出,其中Required_Bins存储的是类库和其他资源;字面的意思Required,是必须文件。 打开Required文件夹,我们看到里面是这样的。 这里有两个类库;可以分析得出,这两个类库是要被引用的。 类库拥有对应的XML,没找到具体使用该XML的方法。所以暂时不去理他。 NHibernate.pdb应该是没有用的。估计是作者忘记删除了。 nhibernate-configuration.xsd和nhibernate-mapping.xsd两个文件暂时不知道要干什么用的。 但看到.xsd文件,第一时间反应,他们应该是用来帮助开发者,快速生成配置文件用的。为了保险起见,我们上网查询一下。...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS8编译安装MySQL8.0.19
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- Red5直播服务器,属于Java语言的直播服务器