首页 > 代码库 > 冒泡排序详解
冒泡排序详解
冒泡排序可以说是排序中一个十分重要的内容,很多时候都会遇到,比如面试,考试等。下面就来写一写冒泡排序,也可以加深一下自己的理解。
冒泡排序原理,依次比较相邻的两个元素,把较大的元素移至后端;每趟排序找出较大的值放在后端。
给定一个数组,例如[2,8,4,6,1];
第一趟排序:将8移至后端
第一次排序:[2,8,4,6,1]; //比较2和8,位置不变
第二次排序:[2,4,8,6,1]; //比较8和4,将8移至4的后面
第三次排序:[2,4,6,8,1]; //比较8和6,将8移至6的后面
第四次排序:[2,4,6,1,8]; //比较8和1,将8移至1的后面
第二趟排序:将6移至后端
第一次排序:[2,4,6,1,8]; //比较2和4,位置不变
第二次排序:[2,4,6,1,8]; //比较4和6,位置不变
第三次排序:[2,4,1,6,8]; //比较6和1,将6移至1的后面
第三趟排序:将4移至后端
第一次排序:[2,4,1,6,8]; //比较2和4,位置不变
第二次排序 : [2,1,4,6,8]; //比较4和1,将4移至1的后面
第四次排序:将2移至后端
第一次排序:[1,2,4,6,8]; //比较2和1,将2移至1的后面
冒泡排序代码如下:
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; } } }
时间复杂度:
1.如果数组是顺序的,则一趟排序即可,进行n-1次比较,时间复杂度为O(n);
2.如果数组是逆序的,则需要n-1趟排序,每次n-i趟比较,时间复杂度为O(n2);
综上,冒泡排序平均时间复杂度为O(n2);
冒泡排序详解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。