冒泡,即像气泡一样一层一层往上冒,冒泡排序就是相邻两个数比较,大的数往后移,这样一次一次往后移的过程中,逐步将最大的排到右边,形成一个有序的数组。完整的代码可以到我的 GitHub 上查看 Algorithm

算法描述

  1. 对于数组 a[n],其长度为 len,另 j = 0,比较 a[j] 与 a[j+1],并将 a[j+1] 赋与较大的值,j++;
  2. 当 j < len - 1,重复操作步骤 1,循环结束后,确立了一个最大值;
  3. 另 i = 1,当 i < len ,重复 步骤 1、步骤2,直到数组排序完成。

算法图解

BubbleSort

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort(int[] arr){
int len = arr.length;
for (int i = 1; i < len; i++) {
for (int j = 0; j < len - i; j++) {
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
//j 完整遍历一次,确认一个最大值
}
}

效率分析

当所有元素都已经由小到大排好时,仍然要依次比较,时间复杂度为 O(n²);

当所有元素都从大到小排列时, 除了比较,还要交换移位操作,最终时间复杂度也是 O(n²)。

在我的机器上运行 10000 个元素排序,所用的时间为:

1
执行时间为:195ms

20000 个元素所用的时间

1
执行时间为:809ms

100000 个元素所用的时间

1
执行时间为:19495ms

冒泡排序的效率非常之低,当数据很多时,排序时间明显增多。