思想
算法描述
- 比较相邻的元素,如果前一个比后一个大,交换之。
- 第一趟排序第1个和第2个一对,比较与交换,随后第2个和第3个一对比较交换,这样直到倒数第2个和最后1个,将最大的数移动到最后一位。
- 第二趟将第二大的数移动至倒数第二位
……
因此需要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/**
* @ClassName: BubbleSortMain
* @Author: fanjiajia
* @Date: 2019/3/4 下午9:15
* @Version: 1.0
* @Description: 冒泡排序
*/
import com.jiajia.ArrayUtil.*; // 按包名导入
public class BubbleSortMain {
public static void main(String[] args) {
int[] arr = {2,5,1,3,8,5,7,4,3};
bubbleSort(arr);
ArrayUtil.print(arr);
}
/**
* 冒泡排序
* @param arr
*/
private static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i -1; j++) { // 这里说明为什么需要-1
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
复杂度
时间复杂度: $O(N^2)$
空间复杂度: $O(1)$
稳定性: 稳定
参考资料
https://www.toutiao.com/a6593273307280179715/?iid=6593273307280179715
最后
此致,敬礼