冒泡排序(空间复杂度，时间复杂度，稳定性分析，代码，图解)_请对冒泡排序算法进行描述,并对其复杂性进行分析

基本原理

对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。如果从小到大排序，这时，较小的数据就会逐个向前移动，好像气泡向上漂浮一样。

特点

升序排序中每一轮比较会把最大的数下沉到最底，所以相互比较的次数每一轮都会比前一轮少一次。

图解

空间复杂度，时间复杂度，稳定性分析

• 冒泡排序法是把N个数通过N-1轮排序，升序排序中大的数往下沉，小的数往上浮，降序排序中小的数往下沉，大的数往上浮

• 冒泡排序需要进行n-1趟冒泡，每一趟需要比较n-i次，最坏情况下需要交换n-1次，故时间复杂度为。冒泡排序的空间复杂度是，因为只需要使用一个临时变量即可。

• 冒泡排序除了本身所使用的的固定空间以外，没有额外的开销，空间复杂度是。平均时间复杂度是，最好时间复杂度是,最坏时间复杂度是。

• 算法稳定性：
  对于算法的稳定性而言，我们先假设，在此时序列中有两个相邻的值为 13 的元素（其它重复元素同理，不是相邻的话在冒泡的过程中也会有相邻的状态），根据判断条件 i > j , 且 A[i] == A[j] ，在做冒泡排序的时候，13 和 另外一个13之间不会发生位置的交换；
  所以，冒泡排序是一种稳定的排序算法。

代码

public class BubbleSort {
 
	public static void main(String[] args) {
		int[] arr= {9,4,1,3,7,8,6,2,5};
		bubbleSort(arr);
		printIntArray(arr);
	}
 
	//冒泡排序
	static void bubbleSort(int[] arr) {
		for(int i=arr.length-1;i>0;i--)
		for (int j = 0; j < i; j++) {
			if(arr[j]>arr[j+1])
				swapIntArray(arr, j, j+1);
		}
	}
	
	//打印整型数组
	public static void printIntArray(int[] arr){
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
		
	//交换整型数组指定位置的元素
	public static void swapIntArray(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
}
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

执行结果：

1 2 3 4 5 6 7 8 9 
1

打印过程的代码

package algorithm;
 
public class BubbleSort {
 
	public static void main(String[] args) {
		int[] arr= {9,4,3,1,3,7,8,6,2,5};
		bubbleSort(arr);
		printIntArray(arr);
	}
 
	//冒泡排序
	static void bubbleSort(int[] arr) {
		for(int i=arr.length-1;i>0;i--) {
			printIntArray(arr);
			System.out.println("第"+(arr.length-i)+"次排序：");
			for (int j = 0; j < i; j++) {
				if(arr[j]>arr[j+1]) {
					swapIntArray(arr, j, j+1);
					System.out.print("索引["+j+"]与["+(j+1)+"]即元素‘"+arr[j+1]+"’与‘"+arr[j]+"’交换：");
					printIntArray(arr);
				}
			}
		}
	}
	
	//打印整型数组
	public static void printIntArray(int[] arr){
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
		
	//交换整型数组指定位置的元素
	public static void swapIntArray(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
}
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
38
39
40

结果:

9 4 3 1 3 7 8 6 2 5 
第1次排序：
索引[0]与[1]即元素‘9’与‘4’交换：4 9 3 1 3 7 8 6 2 5 
索引[1]与[2]即元素‘9’与‘3’交换：4 3 9 1 3 7 8 6 2 5 
索引[2]与[3]即元素‘9’与‘1’交换：4 3 1 9 3 7 8 6 2 5 
索引[3]与[4]即元素‘9’与‘3’交换：4 3 1 3 9 7 8 6 2 5 
索引[4]与[5]即元素‘9’与‘7’交换：4 3 1 3 7 9 8 6 2 5 
索引[5]与[6]即元素‘9’与‘8’交换：4 3 1 3 7 8 9 6 2 5 
索引[6]与[7]即元素‘9’与‘6’交换：4 3 1 3 7 8 6 9 2 5 
索引[7]与[8]即元素‘9’与‘2’交换：4 3 1 3 7 8 6 2 9 5 
索引[8]与[9]即元素‘9’与‘5’交换：4 3 1 3 7 8 6 2 5 9 
4 3 1 3 7 8 6 2 5 9 
第2次排序：
索引[0]与[1]即元素‘4’与‘3’交换：3 4 1 3 7 8 6 2 5 9 
索引[1]与[2]即元素‘4’与‘1’交换：3 1 4 3 7 8 6 2 5 9 
索引[2]与[3]即元素‘4’与‘3’交换：3 1 3 4 7 8 6 2 5 9 
索引[5]与[6]即元素‘8’与‘6’交换：3 1 3 4 7 6 8 2 5 9 
索引[6]与[7]即元素‘8’与‘2’交换：3 1 3 4 7 6 2 8 5 9 
索引[7]与[8]即元素‘8’与‘5’交换：3 1 3 4 7 6 2 5 8 9 
3 1 3 4 7 6 2 5 8 9 
第3次排序：
索引[0]与[1]即元素‘3’与‘1’交换：1 3 3 4 7 6 2 5 8 9 
索引[4]与[5]即元素‘7’与‘6’交换：1 3 3 4 6 7 2 5 8 9 
索引[5]与[6]即元素‘7’与‘2’交换：1 3 3 4 6 2 7 5 8 9 
索引[6]与[7]即元素‘7’与‘5’交换：1 3 3 4 6 2 5 7 8 9 
1 3 3 4 6 2 5 7 8 9 
第4次排序：
索引[4]与[5]即元素‘6’与‘2’交换：1 3 3 4 2 6 5 7 8 9 
索引[5]与[6]即元素‘6’与‘5’交换：1 3 3 4 2 5 6 7 8 9 
1 3 3 4 2 5 6 7 8 9 
第5次排序：
索引[3]与[4]即元素‘4’与‘2’交换：1 3 3 2 4 5 6 7 8 9 
1 3 3 2 4 5 6 7 8 9 
第6次排序：
索引[2]与[3]即元素‘3’与‘2’交换：1 3 2 3 4 5 6 7 8 9 
1 3 2 3 4 5 6 7 8 9 
第7次排序：
索引[1]与[2]即元素‘3’与‘2’交换：1 2 3 3 4 5 6 7 8 9 
1 2 3 3 4 5 6 7 8 9 
第8次排序：
1 2 3 3 4 5 6 7 8 9 
第9次排序：
1 2 3 3 4 5 6 7 8 9 
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
38
39
40
41
42
43