排序算法整理1:冒泡排序及其时间与空间复杂度的计算
发布日期:2021-06-29 02:38:25
浏览次数:4
分类:技术文章
本文共 4413 字,大约阅读时间需要 14 分钟。
今日内容
- 冒泡排序
冒泡排序(Bubble Sort)
- 原理:重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
- 步骤: 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个; 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数; 3.针对所有的元素重复以上的步骤,除了最后一个; 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
- 动图演示:
- 代码实现
//冒泡排序基本做法public class BubbleSort { private static void main(int[] arr) { //第一轮:比4次 for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } System.out.println(Arrays.toString(arr)); //第二轮比3次 for (int i = 0; i < arr.length - 1 - 1; i++) { if (arr[i] > arr[i + 1]) { int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } System.out.println(Arrays.toString(arr)); //第三轮比2次 for (int i = 0; i < arr.length - 1 - 1 - 1; i++) { if (arr[i] > arr[i + 1]) { int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } System.out.println(Arrays.toString(arr)); //第三轮比1次 for (int i = 0; i < arr.length - 1 - 1 - 1 - 1; i++) { if (arr[i] > arr[i + 1]) { int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } System.out.println(Arrays.toString(arr)); }}//代码优化1(双层for循环)public class BubbleSort { public static void main(String []args) { int []arr={ 13,45,34,23,56,23,14,33}; for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } System.out.println(Arrays.toString(arr)); }}//代码优化2:在排序过程中,我们可能会重复的去多次比较已排好的序列,这样就造成了冗余,当数据量大时,会明显的耗时。/*为解决这个问题,我们在这里添加一个lastIndex索引,用于标记最后一次交换的位置(注意,这里是交换不是比较),当交换到arr数组中7之前,也就是下标为4的时候,不再交换,说明后面的已经有序,下次就直接比较到下标为4的位置,后面的不再比较。另外,如果是倒序排正序,则没有优化,比较n*(n-1)/2次。*/public class BubbleSort { public static void main(String []args) { int []arr={ 13,45,34,23,56,23,14,33}; int i = arr.length - 1; int count = 0; // 计数 while (i > 1) { int lastChange = 1; // 记录最后一次交换位置 for (int j = 1; j < i; j++) { // 前面比后面大,则进行交换 if (arr[j] > arr[j + 1]) { arr[j] = arr[j] + arr[j + 1]; arr[j + 1] = arr[j] - arr[j + 1]; arr[j] = arr[j] - arr[j + 1]; lastChange = j; // 每交换一次更新一次 } count++; } i = lastChange; } System.out.println(count); } }
- 时间复杂度与空间复杂度的计算
public class BubbleSort { public static void main(String []args) { //测试时间顺序 int arr[]=new int[10000]; Random r = new Random(); //给数组元素赋值 for(int i = 0;iarr[n + 1]) { int temp = arr[n]; arr[n] = arr[n + 1]; arr[n + 1] = temp; } count++; } } System.out.println(count); }}
- 可以清楚的看到在测试数据量为10000时,双层for循环所需的次数为49995000次以及所耗时间为285ms。
优化代码:public class BubbleSort { public static void main(String []args) { //测试时间顺序 int arr[]=new int[10000]; Random r = new Random(); //给数组元素赋值 for(int i = 0;i1) { int lastChange = 1; // 记录最后一次交换位置 for (int j = 1; j < i; j++) { // 前面比后面大,则进行交换 if (arr[j] > arr[j + 1]) { arr[j] = arr[j] + arr[j + 1]; arr[j + 1] = arr[j] - arr[j + 1]; arr[j] = arr[j] - arr[j + 1]; lastChange = j; // 每交换一次更新一次 } count++; } i = lastChange; } System.out.println(count); } }
-可以清楚的看到在测试数据量为10000时,优化后的冒泡排序所需的次数为49944191次以及所耗时间为189ms。
转载地址:https://blog.csdn.net/yzl109zj125/article/details/117001048 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月30日 20时59分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
laydate日期插件时间
2019-04-29
h5页面微信分享代码
2019-04-29
phpqrcode生成二维码及使用方法
2019-04-29
php获取指定日期的上一个月和下一个月的日期
2019-04-29
jsp脚本、jsp表达式、jsp声明三者的区别。
2019-04-29
python网页解析器
2019-04-29
linux安装svn并设置自启动
2019-04-29
svn常用命令
2019-04-29
python2网页采集案例
2019-04-29
svn的服务端配置
2019-04-29
python3 urllib和requests模块
2019-04-29
Axure常见的几种原型图
2019-04-29
svn的checkout与export的区别与使用
2019-04-29
js实现点击复制功能
2019-04-29
phpquery采集案例
2019-04-29
jsp内置对象request的常用方法
2019-04-29
javascript 0和-0
2019-04-29
iView3.0样式显示问题(Select和DatePicker)
2019-04-29
Gulp常用的一些插件
2019-04-29
Docker:基础知识
2019-04-29