《冒泡排序算法》

发表于 分类于 ， 阅读次数： 本文字数： 1k 阅读时长 ≈ 4 分钟
个人公众号

《算法与数据结构：冒泡排序算法》

冒泡排序算法

算法简介

冒泡排序是一种简单的排序算法，它重复地遍历待排序的元素列表，比较相邻的元素，并在需要时交换它们的位置。每遍历一次列表，至少有一个元素会被移至其正确的位置，这个过程类似于气泡从水底升到水面的过程，因此得名 “冒泡排序”。

关键特点

  • 简单直观：易于理解和实现。
  • 效率较低：对于大量元素的列表，其性能不如更复杂的排序算法。
  • 稳定性：相等的元素在排序后保持原有顺序。

算法工作原理

  • 比较和交换：从列表的开始处开始，比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。
  • 重复过程：对列表的每一对相邻元素执行步骤 1，直到列表的末尾。这完成了列表的一次完整遍历。
  • 重复遍历：重复步骤 1 和 2，每次遍历都会减少最后一个比较的元素。
  • 完成排序：当没有更多元素需要比较时，列表排序完成。

表格演示

为了展示冒泡排序算法的步骤，我会使用一个简单的例子，并通过表格的形式来展示每一步的操作。假设我们有一个数列 [5, 3, 8, 4, 2]，我们将按照冒泡排序的规则对其进行排序。以下是排序的详细步骤：

初始数列: | 5 | 3 | 8 | 4 | 2 |

第一轮比较:

  • 比较 5 和 3，交换位置，因为 5 > 3
  • 比较 5 和 8，不交换，因为 5< 8
  • 比较 8 和 4，交换位置，因为 8 > 4
  • 比较 8 和 2，交换位置，因为 8>2

| 3 | 5 | 4 | 2 | 8 |

第二轮比较:

  • 比较 3 和 5，不交换，因为 3< 5
  • 比较 5 和 4，交换位置，因为 5>4
  • 比较 5 和 2，交换位置，因为 5> 2
  • 此轮不再与 8 比较，因为 8 已经是最大的了

| 3 | 4 | 2 | 5 | 8 |

第三轮比较:

  • 比较 3 和 4，不交换，因为 3< 4
  • 比较 4 和 2，交换位置，因为 4 > 2
  • 此轮不再与 5 和 8 比较

| 3 | 2 | 4 | 5 | 8 |

第四轮比较:

  • 比较 3 和 2，交换位置，因为 3 > 2
  • 此轮不再与 4，5 和 8 比较

| 2 | 3 | 4 | 5 | 8 |

结束:

  • 所有元素均已正确排序

图画演示

创建一个演示数组【3，5，1，2，4】，数组长度为 5，数组表示为 nums[0,5) 左闭右开区间。

img

动画 GIF 演示

冒泡排序算法GIF

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
public class BubbleSort {

    /**
     * 宏观前提  数组左闭右开
     * i 表示进行的第i轮排序
     * nums[0,n-i)未排序
     * nums[n-1,n)已经排序
     * 每轮排序选择未排序中最大的元素放在nums[n-i-1]位置
     * 每轮排序结束  nums[n-i-1]位置 元素确认
     *
     * @param nums 待排序数组
     */
    public static void bubbleSort(int[] nums) {
        int len = nums.length;
        // 每轮排序都将能确定至少一个元素的位置，
        // 共有n个元素，当n-1个元素的位置已经确定，
        // 剩下的一个元素位置必将确认
        // 所以只需要进行n-1轮排序
        for (int i = 0; i < len - 1; i++) {
            // 针对每一轮排序 我们只做一件事
            // 1、在nums[n-i-1]的位置上放上正确的数据
            for (int j = 0; j < len - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    private static void swap(int[] nums, int low, int high) {
        int temp = nums[low];
        nums[low] = nums[high];
        nums[high] = temp;
    }
}

Java 范型实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class BubbleSort {

    public static <E extends Comparable<? super E>> void bubbleSort(E[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if (nums[j].compareTo(nums[j + 1]) > 0) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }
  
    private static <E extends Comparable<? super E>> void swap(E[] nums, int low, int high) {
        E temp = nums[low];
        nums[low] = nums[high];
        nums[high] = temp;
        // help gc
        temp = null;
    }
}

github 项目