博客

详解冒泡排序算法原理与使用方法

冒泡排序算法是一种简单的排序算法，其基本思想是依次比较相邻元素的大小，如果左侧元素大于右侧元素，则进行交换，一轮比较完毕之后，最大的元素就会“冒泡”到数组的末尾。重复进行上述操作，直到数组排序完成。

冒泡排序的时间复杂度为 O(n^2)，在数据量较小的情况下表现良好，但在大规模数据排序时会效率低下。

算法实现

冒泡排序算法可以使用以下的代码实现:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

上述代码使用了Python语言编写，但其思路与其他语言编写的冒泡排序算法是类似的。代码中使用了两层循环嵌套，第一层循环表示进行的轮数，第二层循环表示每轮比较相邻元素的次数。如果相邻元素大小不符合排序要求，则进行交换。

示例说明

下面通过两个示例说明冒泡排序的作用和使用方法。

示例一：对数值型数组进行排序

假设现有一个数组 [4, 2, 1, 3, 5]，需要对其进行升序排序，可以使用冒泡排序算法进行排序。代码如下：

arr = [4, 2, 1, 3, 5]
sorted_arr = bubble_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 3, 4, 5]

可以看到，冒泡排序算法使得原数组中的元素被重新排列，从而使其成为一个按照升序排列的新数组。

示例二：对对象数组进行排序

在实际开发中，我们可能需要对一组对象按照某个属性进行排序。可以使用冒泡排序算法对对象数组进行排序。代码如下：

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __str__(self):
        return f'{self.name} ({self.age})'

def bubble_sort_persons(persons, key):
    n = len(persons)
    for i in range(n):
        for j in range(0, n - i - 1):
            if getattr(persons[j], key) > getattr(persons[j + 1], key):
                persons[j], persons[j + 1] = persons[j + 1], persons[j]
    return persons

persons = [
    Person('张三', 18),
    Person('李四', 22),
    Person('王五', 14),
    Person('赵六', 25),
]
sorted_persons = bubble_sort_persons(persons, 'age')
for person in sorted_persons:
    print(person)

输出结果为：

王五 (14)
张三 (18)
李四 (22)
赵六 (25)

可以看到，对象数组被按照属性 age 进行了排序，并输出了排序后的结果。在实际使用中，我们只需要根据需要修改 Person 类的定义和调用代码即可对不同属性进行排序。

Tags: