黑马程序员技术交流社区
标题:
java 冒泡排序
[打印本页]
作者:
H_shaohui
时间:
2016-5-6 19:38
标题:
java 冒泡排序
冒泡排序法
：关键字较小的记录好比气泡逐趟上浮，关键字较大的记录好比石块下沉，每趟有一块最大的石块沉底。
算法本质：（最大值是关键点，肯定放到最后了，如此循环）每次都从第一位向后滚动比较，使最大值沉底，最小值上升一次，最后一位向前推进（即最后一位刚确定的最大值不再参加比较，比较次数减1）
复杂度： 时间复杂度 O(n2) ，空间复杂度O(1)
3、java实现
1 package
com.sort;
2 3 //稳定 4 public class
冒泡排序 {
5 public static void
main(String[] args) {
6 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8
};
7 System.out.println("排序之前："
);
8 for (int i = 0; i < a.length; i++
) {
9 System.out.print(a
+" "
);
10
}
11 //冒泡排序12 for (int i = 0; i < a.length; i++
) {
13 for(int j = 0; j<a.length-i-1; j++
){
14 //这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了15 if(a[j]>a[j+1
]){
16 int temp =
a[j];
17 a[j] = a[j+1
];
18 a[j+1] =
temp;
19
}
20
}
21
}
22
System.out.println();
23 System.out.println("排序之后："
);
24 for (int i = 0; i < a.length; i++
) {
25 System.out.print(a
+" "
);
26
}
27
}
28 }
假如数组是：int []nums = {5,4,3,2,1};
每一轮比较后的输出如下:
(1) 4,3,2,1,5,
(2) 3,2,1,4,5,
(3) 2,1,3,4,5,
(4) 1,2,3,4,5,
(5) 1,2,3,4,5,
4、分析
冒泡排序是一种稳定的排序方法。
•若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)
•若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)
•起泡排序平均时间复杂度为O(n2)
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2
假如数组是：int []nums = {5,4,3,2,1};