冒泡排序

1、冒泡排序：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2、时间复杂度
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n^2) 平均情况：T(n) = O(n^2)

3、演示图
Image text

4、实现

1
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
27
28
29
30
31
32
33
34
35
36
37
package sort;

public class BubbleSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] a= {1,8,3,7,5};
		bubbleSort(a);
		printArr(a);
	}

	public static void bubbleSort(int [] a) {
		boolean flag=false;//标记某一趟排序是否发生交换，若无交换，说明当前数组已是排序好的数组
		
		for(int i=0;i<a.length-1;i++) {//比length-1趟
			for(int j=1;j<a.length-i;j++) {//每趟排好一个元素（最大的元素沉到最底），下一趟少不必比较这个元素
				if(a[j]<a[j-1]) {
					flag=true;
					int temp=a[j];
					a[j]=a[j-1];
					a[j-1]=temp;
				}
			}
			
			if(!flag) {//没有发生交换则跳出循环
				break;
			}
			//System.out.println(flag);
		}
	}
	
	public static void printArr(int [] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
	}
}