冒泡排序顾名思义就是整个过程就像气泡一样往上升,单向冒泡排序的基本思想是(假设由小到大排序):对于给定的 n 个记录,从第一个记录开始依次对相邻的两个记录进行比较,当前面的记录大于后面的记录时,交换位置,进行一轮比较和换位后,n 个记录中的最大记录将位于第 n位;然后对前(n-1)个记录进行第二轮比较;重复该过程直到进行比较的记录只剩下一个为止。
以数组 {45,3,2,5,7,8,32,9,1,22,0} 为例,冒泡排序的具体步骤如下:
[3, 2, 5, 7, 8, 32, 9, 1, 22, 0, 45]
[2, 3, 5, 7, 8, 9, 1, 22, 0, 32, 45]
[2, 3, 5, 7, 8, 1, 9, 0, 22, 32, 45]
[2, 3, 5, 7, 1, 8, 0, 9, 22, 32, 45]
[2, 3, 5, 1, 7, 0, 8, 9, 22, 32, 45]
[2, 3, 1, 5, 0, 7, 8, 9, 22, 32, 45]
[2, 1, 3, 0, 5, 7, 8, 9, 22, 32, 45]
[1, 2, 0, 3, 5, 7, 8, 9, 22, 32, 45]
[1, 0, 2, 3, 5, 7, 8, 9, 22, 32, 45]
[0, 1, 2, 3, 5, 7, 8, 9, 22, 32, 45]
程序示例如下:
/**
* 冒泡排序: 先将最大的数沉下去,再进行第二次-1 的排序
*/
public class BubbleSorting {
//temp 是过度字段
int i,j,temp;
//排序方法:从小到大排序
public void sort(Integer[] arr){
for(int i =1;i<arr.length;i++) {
for(int j=0;j<arr.length-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.asList(arr).toString());
}
}
public static void main(String[] args) {
Integer[] s = {45,3,2,5,7,8,32,9,1,22,0};
new BubbleSorting().sort(s);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
程序输入为:[0, 1, 2, 3, 5, 7, 8, 9, 22, 32, 45]
总结:若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数 C 和记录移动次数 M 均达到最小值:所以,冒泡排序最好的时间复杂度为O(n)
;若初始文件是反序的,需要进行n-1
趟排序。每趟排序要进行n-i
次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:O(n^{2})
冒泡排序的最坏时间复杂度为:O(n^{2})
综上,因此冒泡排序总的平均时间复杂度为:O(n^{2})
。