冒泡排序
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长5分钟
冒泡排序是一个简单的排序算法，它通过循环不断的比较和交换相邻的元素，直到所有元素有序。最好的情况是当数组已经有序时，时间复杂度是O(N)，最坏的情况是当数组是反序时，时间复杂度是O(N^2)，平均时间复杂度是O(N^2)。
算法的主要思路是
- 从第一个元素开始，比较当前元素和下一个元素，如果当前元素大于下一个元素，则交换，否则不操作。
- 当操作结束后，最大的元素将被移动到数组末尾。
- 继续对前n-1个元素执行第1、2步，操作结束后，第二大的元素将被移动到数组倒数第二的位置。
- 继续对前n-2个元素执行第1、2步，操作结束后，第三大的元素将被移动到数组倒数第三的位置。
- ....
- 直到最小的元素被移动到数组第一个位置。
比如数组[4, 2, 1, 3, 7, 6, 5]冒泡排序过程如下
1/6
从上面的演示可以看出冒泡排序可能在没有执行完所有比较交换就已经有序了，所以可以进行优化，但一轮完成之后发现没有交换过，则说明数组已经有序，完成排序，冒泡排序算法未优化版和优化版实现如下。
1import java.util.Arrays;
2
3public class Main {
4
5 public static void main(String[] args) {
6 int[] arr = {4, 2, 1, 3, 7, 6, 5};
7 bubbleSort(arr);
8 System.out.println(Arrays.toString(arr));
9 }
10
11 /**
12 * 冒泡排序未优化版
13 * 从第一个元素开始比较交换，每一轮比较交换后，
14 * 会有一个元素被移动到正确的位置，然后继续比较交换前面的元素。
15 *
16 * @param arr 待排序的数组
17 */
18 public static void bubbleSort(int[] arr) {
19 for (int i = 0; i < arr.length - 1; i++) {
20 for (int j = 0; j < arr.length - i - 1; j++) {
21 if (arr[j] > arr[j + 1]) {
22 swap(arr, j, j + 1);
23 }
24 }
25 }
26 }
27
28 /**
29 * 冒泡排序优化版
30 * 从第一个元素开始比较交换，每一轮比较交换后，
31 * 会有一个元素被移动到正确的位置，然后继续比较交换前面的元素。
32 *
33 * @param arr 待排序的数组
34 */
35 public static void bubbleSortTurbo(int[] arr) {
36 for (int i = 0; i < arr.length - 1; i++) {
37 boolean swapped = false;
38 for (int j = 0; j < arr.length - i - 1; j++) {
39 if (arr[j] > arr[j + 1]) {
40 swap(arr, j, j + 1);
41 swapped = true;
42 }
43 }
44 if (!swapped) {
45 break;
46 }
47 }
48 }
49
50 /**
51 * 交换元素
52 *
53 * @param arr 数组
54 * @param i，j 待交换的位置
55 */
56 public static void swap(int[] arr, int i, int j) {
57 int temp = arr[i];
58 arr[i] = arr[j];
59 arr[j] = temp;
60 }
61}
62注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
冒泡排序相对于快速排序、归并排序等算法效率比较低，但是实现比较简单，如果对于算法效率要求不高，或者规模很小的数据可以使用冒泡排序。
排序算法冒泡排序