排序算法系列——冒泡排序

冒泡排序是交换排序的一种,其思想是从序列头部开始逐步往后遍历,每次遍历比较相邻两个元素,如果顺序不对则交换,n-1次遍历之后序列就完成了排序。由于每次遍历都是把最大的元素一步步让最后移动,类似于水泡慢慢浮出水面,于是得名冒泡算法。冒泡算法的思想很简单,实现起来也很容易,但是效率太低,所以即使是小数据量也很少推荐使用冒泡算法,更多的使用直接插入排序。

基本思想

从待排序序列头部开始循环遍历n-1次,每次遍历比较相邻两个元素,如果顺序不对则交换,也就是说如果你想要从小到大排列,那么如果相邻两个元素比较结果是前面的大于后面的,则交换就可以了,那么通过一次遍历最大的元素就到达了序列的尾部,n-1次遍历之后序列就完成了排序。这里显然有可优化的空间,下面会提到。

实现要点

第i次(i=0…n-1)遍历从0开始比较到n-1-i(n序列长度),因为每次遍历都会将未排序部分最大的元素移动到序列尾部,所以序列尾部是有序的,故在之后的遍历过程中无需继续比较有序的部分。
算法改进
该算法有两处可优化的地方:

  • 如果一次遍历过程中未发生任何交换,即所有相邻元素的顺序都是正确的,则说明整个序列已经完成排序,故无需继续遍历。
  • 每次遍历过程中记录下最后一次发生遍历的位置,则在改位置之后的部分已经是有序的,下次遍历时就可以提前结束。

实验表明以上两种改进之后的效率并未有太大的提高,第一种改进效率反而比为改进的低,第二种改进效率稍微提高一点点。虽然这两种改进从理论上来看是有一定的优化的,但是测试时使用的序列一般都是随机的,即在n-1次遍历之前完成排序以及部分有序的可能性都很小,所以这两种改进的效果都不是很明显,可能根本不会发生,反而由于加入了一些逻辑判断反而导致效率降低。不过如果是真是数据,那么之前提到的两种情况还是很可能发生的。

Java实现

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
package com.vicky.sort;

import java.util.Random;

/**
* 交换排序:冒泡排序
*
* 时间复杂度:O(n^2)
*
* 空间复杂度:O(1)
*
* 稳定性:稳定
*
* @author Vicky
*
*/

public class BubbleSort {

/**
* 未改进的冒泡排序
*
* @param <T>
* @param data
*/

public static <T extends Comparable<T>> void sort(T[] data) {
long start = System.nanoTime();
if (null == data) {
throw new NullPointerException("data");
}
if (data.length == 1) {
return;
}
// n-1趟遍历
for (int i = 0; i < data.length - 1; i++) {
// 每次遍历从0开始依次比较相邻元素
for (int j = 0; j < data.length - 1 - i; j++) {
// 前面元素>后面元素则交换
if (data[j].compareTo(data[j + 1]) > 0) {
T temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
System.out.println("sort, use time:" + (System.nanoTime() - start)
/ 1000000);
}

/**
* 改进后冒泡排序
*
* 改进原理:如果一次遍历过程未发生交换,则说明序列已经是有序的,故无需再进行遍历。
*
* @param <T>
* @param data
*/

public static <T extends Comparable<T>> void sortImprove(T[] data) {
long start = System.nanoTime();
if (null == data) {
throw new NullPointerException("data");
}
if (data.length == 1) {
return;
}
boolean exchange = false;// 记录一趟遍历是否发生交换
// n-1趟遍历
for (int i = 0; i < data.length - 1; i++) {
// 每次遍历从0开始依次比较相邻元素
for (int j = 0; j < data.length - 1 - i; j++) {
// 前面元素>后面元素则交换
if (data[j].compareTo(data[j + 1]) > 0) {
T temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
exchange = true;
}
}
// 如果本次遍历未发生交换,则说明序列已是有序的,则无需继续遍历
if (!exchange) {
return;
}
}
System.out.println("sortImprove1, use time:"
+ (System.nanoTime() - start) / 1000000);
}

/**
* 改进后冒泡排序
*
* 改进原理:在冒泡排序的每趟扫描中,记住最后一次交换发生的位置lastexchange也能有所帮助。因为该位置之后的部分已经是有序的(未发生交换,
* 所以是有序),
* 故下一趟排序开始的时候,只需处理0到lastexchange部分,lastexchange到n-1是有序区。同时如果未发生交换则退出即可
*
* @param <T>
* @param data
*/

public static <T extends Comparable<T>> void sortImprove2(T[] data) {
long start = System.nanoTime();
if (null == data) {
throw new NullPointerException("data");
}
if (data.length == 1) {
return;
}
int lastChange = data.length - 1;// 记录一趟遍历最后一次发生交换的位置,该位置之后是有序的
// 上次遍历发生交换则lastChange>0,继续遍历
while (lastChange > 0) {
// 本次遍历从0开始到上次遍历最后一次交换的位置结束
int end = lastChange;
lastChange = 0;
// 每次遍历从0开始依次比较相邻元素
for (int j = 0; j < end; j++) {
// 前面元素>后面元素则交换
if (data[j].compareTo(data[j + 1]) > 0) {
T temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
lastChange = j + 1;
}
}
}
System.out.println("sortImprove2, use time:"
+ (System.nanoTime() - start) / 1000000);
}

public static void main(String[] args) {
// 用于记录三种冒泡排序的用时
long[] useTime1 = new long[10];
long[] useTime2 = new long[10];
long[] useTime3 = new long[10];
// 循环测试10次,取均值
for (int times = 0; times < 10; times++) {
// 构建10000个元素的序列进行排序
Random ran = new Random();
Integer[] data = new Integer[10000];
for (int i = 0; i < data.length; i++) {
data[i] = ran.nextInt(10000000);
}
// 使用System.arraycopy复制三个数组分别用于排序
Integer[] data1 = new Integer[data.length];
Integer[] data2 = new Integer[data.length];
Integer[] data3 = new Integer[data.length];
System.arraycopy(data, 0, data1, 0, data.length);
System.arraycopy(data, 0, data2, 0, data.length);
System.arraycopy(data, 0, data3, 0, data.length);
// 分别记录三种冒泡排序的用时
long start = System.nanoTime();
BubbleSort.sort(data1);
useTime1[times] = (System.nanoTime() - start) / 1000000;
// SortUtils.printArray(data1);
start = System.nanoTime();
BubbleSort.sortImprove(data2);
useTime2[times] = (System.nanoTime() - start) / 1000000;
start = System.nanoTime();
// SortUtils.printArray(data2);
BubbleSort.sortImprove2(data3);
useTime3[times] = (System.nanoTime() - start) / 1000000;
// SortUtils.printArray(data3);
}
// 计算用时最大值,最小值,均值
long[] res1 = SortUtils.countArray(useTime1);
long[] res2 = SortUtils.countArray(useTime2);
long[] res3 = SortUtils.countArray(useTime3);
System.out.println("method\tmax\tmin\tavg\t");
System.out.println("sort" + "\t" + res1[0] + "\t" + res1[1] + "\t"
+ res1[2]);
System.out.println("sortImprove" + "\t" + res2[0] + "\t" + res2[1]
+ "\t" + res2[2]);
System.out.println("sortImprove2" + "\t" + res3[0] + "\t" + res3[1]
+ "\t" + res3[2]);
// 测试结果,第一种改进方法效率比不改进还差一些,
// 可能由于出现提前完成排序的可能性较小,每次遍历加入了过多的赋值以及判断操作导致效率反而降低
// 第二种改进方法还是有一些效果的
// method max min avg
// sort 1190 1073 1123
// sortImprove 1258 1097 1146
// sortImprove2 1205 1056 1099
}
}
效率分析

(1)时间复杂度
O(n^2)
冒泡排序最好的时间复杂度是O(n),一次遍历即可,无需交换(第一种改进)。最坏情况需要遍历n-1次,比较且交换n-1-i次,故时间复杂度是O(n^2)。
(2)空间复杂度
O(1)
从空间来看,它只需要一个元素的辅助空间,用于元素的位置交换O(1)。
(3)稳定性
稳定
排序过程中只有相邻两个元素会发生交换,同时为了减少交换次数相同的元素不会进行交换,所以两个相同元素的相对位置不会发生改变。