一.什么是冒泡排序
1.不断比较两个相邻元素,将大的往后或者往前排,就像水里的泡泡一样,越往后越接近水面泡泡体积越大,由此得名.
用图来说明:
冒泡排序
2.用java代码实现冒泡排序
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
2 // ============================= 第0版 开始 ======================
3 @Test
4 public void sort01() {
5 int []arr = {1, 2, 5, 6, 22, 23, 50, 43, 65, 78, 88};
6 System.out.println("原始数组:" + Arrays.toString(arr) + ",数组长度" +arr.length);
7 System.out.println("第0版 冒泡排序");
8 firstBubbleSort0(arr);
9 System.out.println("排序后数组" + Arrays.toString(arr));
10 }
11
12
13 /**
14 * 普通版 第0版冒泡
15 * @param array
16 */
17 private void firstBubbleSort0(int[] array) {
18 int ifTimes = 0;
19 int swapTimes = 0;
20 for (int i = 0; i < array.length; i++) {
21 for (int j = 0; j < array.length -1; j++) {
22 // if次数
23 ifTimes ++;
24
25 if (array[j] > array[j+1]) {
26 int temp;
27 temp = array[j];
28 array[j] = array[j+1];
29 array[j+1] = temp;
30 swapTimes ++ ;
31 }
32 }
33 System.out.println("第" + i+ "次后结果为:" + Arrays.toString(array));
34 }
35 System.out.println("if判断次数ifTimes = " + ifTimes);
36 System.out.println("发生交换次数swapTimes = " + swapTimes);
37
38 }
39 // ============================= 第0版 结束 ======================
40
41
原始数组:[1, 2, 5, 6, 22, 23, 50, 43, 65, 78, 88]数组长度11
第0版 冒泡排序
第0次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第1次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第2次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第3次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第4次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第5次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第6次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第7次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第8次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第9次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第10次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
if判断次数ifTimes = 110
发生交换次数swapTimes = 1
排序后数组[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
可以看出冒泡排序的空间复杂度为O(1),时间负责度为O(n^2)
3.对于每轮排出来的最后(大)元素,其实可以不参与接下来的排序
一起来看看代码实现(在内部循环中每次遍历终点 array.length – i,i为外层循环 )
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
2 // ============================= 第一版 开始 ======================
3 @Test
4 public void testUnSortArray() {
5 int []arr = {43, 22, 6, 5, 23, 2, 50, 65, 78, 88, 1};
6 System.out.println("原始数组:" + Arrays.toString(arr));
7 firstBubbleSort(arr);
8 System.out.println("排序后数组" + Arrays.toString(arr));
9 }
10
11
12 /**
13 * 普通版 第一版冒泡
14 * @param array
15 */
16 private void firstBubbleSort(int[] array) {
17 int ifTimes = 0;
18 int swapTimes = 0;
19 for (int i = 0; i < array.length; i++) {
20 for (int j = 0; j < array.length -i -1; j++) {
21 // if次数
22 ifTimes ++;
23
24 if (array[j] > array[j+1]) {
25 int temp;
26 temp = array[j];
27 array[j] = array[j+1];
28 array[j+1] = temp;
29 swapTimes ++ ;
30 }
31 }
32 System.out.println("第" + i+ "次后结果为:" + Arrays.toString(array));
33 }
34 System.out.println("ifTimes = " + ifTimes);
35 System.out.println("swapTimes = " + swapTimes);
36
37 }
38
39
打印结果:
原始数组:[43, 22, 6, 5, 23, 2, 50, 65, 78, 88, 1]
第0次后结果为:[22, 6, 5, 23, 2, 43, 50, 65, 78, 1, 88]
第1次后结果为:[6, 5, 22, 2, 23, 43, 50, 65, 1, 78, 88]
第2次后结果为:[5, 6, 2, 22, 23, 43, 50, 1, 65, 78, 88]
第3次后结果为:[5, 2, 6, 22, 23, 43, 1, 50, 65, 78, 88]
第4次后结果为:[2, 5, 6, 22, 23, 1, 43, 50, 65, 78, 88]
第5次后结果为:[2, 5, 6, 22, 1, 23, 43, 50, 65, 78, 88]
第6次后结果为:[2, 5, 6, 1, 22, 23, 43, 50, 65, 78, 88]
第7次后结果为:[2, 5, 1, 6, 22, 23, 43, 50, 65, 78, 88]
第8次后结果为:[2, 1, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第9次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第10次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
if判断次数ifTimes = 55
发生交换次数swapTimes = 22
排序后数组[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
时间复杂度为O(n*(n-1)/2)
冒泡排序就算完成了,好了你已经完全掌握了冒泡排序.(如果你真这样想,那你就天真了,文章也应该结束了).
二.冒泡排序优化
1.如果原来的数组接近完全排序
假如数组:
1, 2, 5, 6, 22, 23, 50, 43, 65, 78, 88
当第一轮排序完成后,得到结果
1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88
2.如果还是使用原始的冒泡排序(第一版)
原始数组:[1, 2, 5, 6, 22, 23, 50, 43, 65, 78, 88]
第一版 冒泡排序
第0次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第1次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第2次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第3次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第4次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第5次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第6次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第7次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第8次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第9次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
第10次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
if判断次数ifTimes = 55
发生交换次数swapTimes = 1
排序后数组[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
我们发现第0次遍历后,数组已经是完全排序.后面的遍历其实没有必要.
3.来了来了,第二版代码
每次内部循环完之后,判断数组是否已经是有序状态
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
44
45
46
47
48
2 @Test
3 public void sort22() {
4 int []arr = {1, 2, 5, 6, 22, 23, 50, 43, 65, 78, 88};
5 System.out.println("原始数组:" + Arrays.toString(arr));
6 System.out.println("第二版 冒泡排序(如果数组已经有序,结束排序)");
7 sortArrayWithAllArrayIsSorted(arr);
8 System.out.println("排序后数组" + Arrays.toString(arr));
9 }
10
11 /**
12 * 对已经排序的 可以减少开销, 当数组已经是排序状态后 不会继续进行
13 * 判断目标是 整个 数组是否已经排序好
14 * @param array
15 */
16 private void sortArrayWithAllArrayIsSorted(int[] array) {
17 int ifTimes = 0;
18 int swapTimes = 0;
19
20 for (int i = 0; i < array.length; i++) {
21 // 是否已经排序好了(是否发生互换 否定)
22 boolean isSorted = true;
23 for (int j = 0; j < array.length - 1 - i ; j++) {
24 // if次数
25 ifTimes ++;
26
27 if (array[j] > array[j+1]) {
28 int temp;
29 temp = array[j];
30 array[j] = array[j+1];
31 array[j+1] = temp;
32 isSorted = false;
33 swapTimes ++ ;
34 }
35 }
36 System.out.println("第" + i+ "次后结果为:" + Arrays.toString(array) + ",isSorted=" + isSorted);
37 // 如果没有互换 说明已经排序完成
38 if (isSorted) {
39 break;
40 }
41 }
42 System.out.println("if判断次数ifTimes = " + ifTimes);
43 System.out.println("发生交换次数swapTimes = " + swapTimes);
44 }
45
46
47 // ============================= 第二版 结束 ======================
48
3.1 使用该代码排序接近排序的数组
原始数组:[1, 2, 5, 6, 22, 23, 50, 43, 65, 78, 88]
第二版 冒泡排序(如果数组已经有序,结束排序)
第0次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第1次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=true
if判断次数ifTimes = 19
发生交换次数swapTimes = 1
排序后数组[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
这种接近完全排序的数组,在这种情况下优势明显.
3.2 如果数组不是接近完全排序
使用第二版 冒泡排序,排序下列数组
原始数组:[2, 5, 6, 1, 22, 23, 43, 50, 65, 78, 88]
第0次后结果为:[2, 5, 1, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第1次后结果为:[2, 1, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第2次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第3次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=true
if判断次数ifTimes = 34
发生交换次数swapTimes = 3
[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
相比较于第一版,还是减少了很多遍历比较次数.
4.如果数组部分有序,只需要遍历无序部分.
观察3.2中例子, 数组中 22, 23, 43, 50, 65, 78, 88 部分不需要排序,那么遍历的时候能不能把这部分排除呢?
所以咱们第三版排序,在第二版的基础上考虑部分有序,遍历到无序 和 有序的分界处就可以了.
上菜:
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
2 public void sort32() {
3 int []arr = {2, 5, 6, 1, 22, 23, 43, 50, 65, 78, 88};
4 System.out.println("原始数组:" + Arrays.toString(arr));
5 System.out.println("第三版 冒泡排序(遍历到无序和有序的边界)");
6 sortArrayWithPartyArrayIsSorted(arr);
7 System.out.println("排序后数组" + Arrays.toString(arr));
8 }
9
10 /**
11 * 遍历到无序和有序的边界
12 * 判断目标是 部分(前半无序,后半有序 会减少if)
13 * @param array
14 */
15 private void sortArrayWithPartyArrayIsSorted(int[] array) {
16
17 int ifTimes = 0;
18 int swapTimes = 0;
19
20 // 最后一次发生交换的地方
21 int lastSwapIndex = 0;
22
23 // 无序部分长度, 每次比较只需要比到这里为止
24 int unSortBorder = array.length -1;
25
26 for (int i = 0; i < array.length; i++) {
27 // 是否已经排序好了(是否发生互换 否定)
28 boolean isSorted = true;
29 for (int j = 0; j < unSortBorder; j++) {
30 // for次数
31 ifTimes ++;
32
33 if (array[j] > array[j+1]) {
34 int temp;
35 temp = array[j];
36 array[j] = array[j+1];
37 array[j+1] = temp;
38
39 isSorted = false;
40 // 当本轮for完成 j 到 array.length 的位置元素已经排序,下轮不需要遍历
41 lastSwapIndex = j;
42
43 swapTimes ++ ;
44 }
45 }
46 System.out.println("第" + i+ "次后结果为:" + Arrays.toString(array) + ",isSorted=" + isSorted);
47 // 如果没有互换 说明已经排序完成
48 // 更新边界
49 unSortBorder = lastSwapIndex;
50
51 if (isSorted) {
52 break;
53 }
54
55 }
56 System.out.println("if判断次数ifTimes = " + ifTimes);
57 System.out.println("发生交换次数swapTimes = " + swapTimes);
58 }
59 // ============================= 第三版 结束 ======================
60
原始数组:[2, 5, 6, 1, 22, 23, 43, 50, 65, 78, 88]
第三版 冒泡排序(遍历到无序和有序的边界)
第0次后结果为:[2, 5, 1, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第1次后结果为:[2, 1, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第2次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第3次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=true
if判断次数ifTimes = 13
发生交换次数swapTimes = 3
排序后数组[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88]
和例子3.2中同样的数组,减少了21次if判断.
5.刚刚我们只考虑了数组的一边是否有边界(有序无序边界),我们能不能考虑数组两边是否有边界呢
思路:i是偶数从左到右冒大泡, 如果i是基数 从右到左冒小泡.
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
2 @Test
3 public void sort43() {
4 int []arr = {2, 5, 6, 22, 23, 43, 50, 65, 78, 88, 1};
5 sortArrayWithDoublePartyArrayIsSorted(arr);
6 System.out.println(Arrays.toString(arr));
7 }
8
9 /**
10 * 对已经排序的 可以减少开销, 当数组已经是排序状态后 不会继续进行
11 * 判断目标是 双边界(从两边观察 是否有已经排好序的部分) 数组是否已经排序好
12 * @param array
13 */
14 private void sortArrayWithDoublePartyArrayIsSorted(int[] array) {
15 int temp;
16 int ifTimes = 0;
17 int swapTimes = 0;
18
19 // 最后一次发生交换的地方
20 int lastLeftSwapIndex = 0;
21 int lastRightSwapIndex = array.length -1;
22
23 for (int i = 0; i < array.length; i++) {
24 // 是否已经排序好了(是否发生互换 否定)
25 boolean isSorted = true;
26
27 // 每次从第个开始判断if
28 int beginBorder = lastLeftSwapIndex;
29 // 无序部分长度, 每次比较只需要比到这里为止
30 int endBorder = lastRightSwapIndex;
31
32 if(i % 2 == 0) {
33 for (int j = beginBorder; j < endBorder; j++) {
34 // if次数
35 ifTimes ++;
36 //
37 if (array[j] > array[j+1]) {
38 temp = array[j];
39 array[j] = array[j+1];
40 array[j+1] = temp;
41
42 isSorted = false;
43 // 当本轮for完成 j 到 array.lenght 的位置元素已经排序
44 lastRightSwapIndex = j;
45
46 // test 代码
47 swapTimes ++ ;
48 }
49 }
50 } else {
51 for (int j = endBorder - 1; j >= 0; j--) {
52 // if次数
53 ifTimes++;
54 //
55 if (array[j] > array[j + 1]) {
56 temp = array[j];
57 array[j] = array[j + 1];
58 array[j + 1] = temp;
59
60 isSorted = false;
61 // 当本轮for完成 endBorder - j 到 endBorder 的位置元素已排序排序
62 lastLeftSwapIndex = j;
63
64 // test 代码
65 swapTimes++;
66 }
67 }
68 }
69 System.out.println("第" + i+ "次后结果为:" + Arrays.toString(array) + ",isSorted=" + isSorted);
70
71 // 如果没有互换 说明已经排序完成
72 if (isSorted) {
73 break;
74 }
75 }
76 System.out.println("if判断次数ifTimes = " + ifTimes);
77 System.out.println("发生交换次数swapTimes = " + swapTimes);
78 }
79
以数组:[ 2, 5, 6, 22, 23, 43, 50, 65, 78, 88, 1 ] 为例
第三版结果:
原始数组:[2, 5, 6, 22, 23, 43, 50, 65, 78, 88, 1]
第三版 冒泡排序(遍历到无序和有序的边界)
第0次后结果为:[2, 5, 6, 22, 23, 43, 50, 65, 78, 1, 88],isSorted=false
第1次后结果为:[2, 5, 6, 22, 23, 43, 50, 65, 1, 78, 88],isSorted=false
第2次后结果为:[2, 5, 6, 22, 23, 43, 50, 1, 65, 78, 88],isSorted=false
第3次后结果为:[2, 5, 6, 22, 23, 43, 1, 50, 65, 78, 88],isSorted=false
第4次后结果为:[2, 5, 6, 22, 23, 1, 43, 50, 65, 78, 88],isSorted=false
第5次后结果为:[2, 5, 6, 22, 1, 23, 43, 50, 65, 78, 88],isSorted=false
第6次后结果为:[2, 5, 6, 1, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第7次后结果为:[2, 5, 1, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第8次后结果为:[2, 1, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第9次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第10次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=true
if判断次数ifTimes = 55
发生交换次数swapTimes = 10
第四版结果:
原始数组:[2, 5, 6, 22, 23, 43, 50, 65, 78, 88, 1]
第四版 冒泡排序(考虑双向边界)
第0次后结果为:[2, 5, 6, 22, 23, 43, 50, 65, 78, 1, 88],isSorted=false
第1次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=false
第2次后结果为:[1, 2, 5, 6, 22, 23, 43, 50, 65, 78, 88],isSorted=true
if判断次数ifTimes = 28
发生交换次数swapTimes = 10
第四版结果明显优于第三版结果,但是第四版缺点就是代码量复杂.
