首页 > 代码库 > 算法大神之路----排序(冒泡排序法)
算法大神之路----排序(冒泡排序法)
冒泡排序法
冒泡排序法又称为交换排序法,是由观察水中冒泡变化构思而成,气泡随着水深压力而改变.气泡在水底时,水压最大,气泡最小,而气泡慢慢浮上水面时,气泡所受压力最小,体积慢慢变大.
冒泡排序比较方式是从第一个元素开始,比较相邻的元素大小,如果大小顺序有误,则对调后进行下一个元素比较.直到所有元素满足关系为止.
冒泡排序法分析
- 冒泡排序法平均情况下,需要比较(n-1)/2次,时间复杂度为O(n2),最好的情况只需要扫描一次,不用操作,即作n-1次比较,时间复杂度为O(n).
- 由于冒泡排序为相邻两者相互比较对调,并不会改变其原本排列的顺序,所以是稳定的排序法
- 只需要一个额外的空间,所以空间复杂度最佳
- 这个排序法适用于数据量小,或者有部分数据已经排序过的情况
代码示例:
import java.util.Random; /** * 算法大神之路----排序(冒泡排序法) */ public class Study01 { public static void main(String[] args) { //新建一个数组 int[] arr = new int[6]; Random r = new Random(); for (int i = 0; i < arr.length; i++) { //使用随机数给数组赋值 arr[i] = r.nextInt(50); } System.out.print("原数组为:"); paint(arr); System.out.println("-----排序-----"); //使用冒泡排序法进行排序,最差情况下 for (int i = arr.length-1; i >=0; i--) { //比较当前数和后一个数,谁大,谁放后面 for (int j = 0; j < i; j++) { if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.print("扫描第"+(arr.length-i)+"次结果为:"); paint(arr); } } public static void paint(int[] arr){ for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+"\t"); } System.out.println(); } }
结果:
原数组为:34 41 24 36 15 21 -----排序----- 扫描第1次结果为:34 24 36 15 21 41 扫描第2次结果为:24 34 15 21 36 41 扫描第3次结果为:24 15 21 34 36 41 扫描第4次结果为:15 21 24 34 36 41 扫描第5次结果为:15 21 24 34 36 41 扫描第6次结果为:15 21 24 34 36 41
可见:
- 第一次扫描时候,把第二个数41一直比较到后面去了
- 第二次扫描则是比较了,把36放到倒数第二个数
- ...
- 最后当第四次扫描的时候,已经排好序.最差情况下需要扫描"数组元素"次,一般,想要优化的话,即在程序中设置,当扫描到已经符合要求后,就直接停止扫描即可
算法大神之路----排序(冒泡排序法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。