排序算法之冒泡排序

80000长度的数据值在[0,800000)之间的数据本机使用冒泡排序,耗时10s;

1. 基本介绍

​ 冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始), 依次比较
相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。

1.1 优化

​ 因排序的过程中,各元素不断接近自己的位置, 如果一趟比较下来没有进行过交换 , 就说明序列有序,因此要在
排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化,可以在冒泡排
序写好后,在进行)

1.2 演示冒泡过程

  • 一共进行 数组的大小-1 次 大的循环
  • 每一趟排序的次数在逐渐的减少
  • 如果我们发现在某趟排序中,没有发生一次交换, 可以提前结束冒泡排序。这个就是优化

2. 冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  int[] array =  {3, 9, -1, 10, 20};
System.out.println("排序前的数组:" + Arrays.toString(array));

// 普通的冒泡排序,升序
int temp = 0;
for (int j = 0; j < array.length; j++) {

for (int i = 0; i < array.length - 1 - j; i++) {
if (array[i] > array[i + 1]) {
temp = array[i + 1];
array[i + 1] = array[i];
array[i] = temp;
}
}

}

System.out.println("排序后的arr = " + Arrays.toString(array));

3. 优化冒泡排序

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
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
80
81
82
83
84
public class BobbleSort {

public static void main(String[] args) {

}

/**
* 冒泡排序的方法
*
* @param str asc是升序 desc是降序 ,也可以使用boolean来决定升序还是降序
* @param arr 需要排序的数组
*/
public static void bubbleSort(int[] arr, String str) {

int temp = 0;
boolean flag = false;

if ("".equals(str) || str == null) {
System.out.println("请输入排序的方式:asc or desc !!!");
return;
}

if (arr.length <= 1) {
System.out.println("输入的数组的数据不需要排序!");
return;
}

// 升序的方法
if (str == "asc") {
int countAsc = 0;
for (int j = 0; j < arr.length; j++) {

for (int i = 0; i < arr.length - 1 - j; i++) {
if (arr[i] > arr[i + 1]) {
flag = true;
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
countAsc++;

}
// 优化冒泡排序的手段
if (!flag) {
break;
} else {
flag = false;
}
}

System.out.println("冒泡升序排序优化后的比较的次数countAsc:" + countAsc);

} else if (str == "desc") {// 降序的排列方

int countDesc = 0;

for (int j = 0; j < arr.length; j++) {

for (int i = 0; i < arr.length - 1 - j; i++) {
if (arr[i] < arr[i + 1]) {
flag = true;
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
countDesc++;
}
// 优化冒泡排序的手段
if (!flag) {
break;
} else {
flag = false;
}

}
System.out.println("冒泡降序排序优化后的比较的次数countDesc:" + countDesc);

} else {
throw new RuntimeException("排序方案输入有误!");
}

}

}

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
38
39
40
41
42
public class BobbleSort {

public static void main(String[] args) {



int[] array = new int[80];
for (int i = 0; i < array.length; i++) {
array[i] = (int)(Math.random()*800);
}

System.out.println("排序前的数组:" + Arrays.toString(array));

// 普通的冒泡排序,升序
int temp = 0;
int count = 0;
for (int j = 0; j < array.length; j++) {
for (int i = 0; i < array.length - 1 - j; i++) {
if (array[i] > array[i + 1]) {
temp = array[i + 1];
array[i + 1] = array[i];
array[i] = temp;
}
count++;
}
}

System.out.println("未优化前的比较的次数:" + count);
System.out.println("排序后的arr = " + Arrays.toString(array));
System.out.println("===============分割线==============");




// bubbleSort(array, "desc");
// System.out.println("降序后的arr = " + Arrays.toString(array));


bubbleSort(array, "asc");
System.out.println("升序后的arr = " +Arrays.toString(array));

}