16 简单算法实践之实现一个排序算法

在上一篇中，我们探讨了如何实现一个简单的查找算法。此次，我们将继续深入学习，实践一个常见的排序算法：冒泡排序。通过这一算法，我们将了解如何对一组数字进行排序，同时加深对算法运作机制的理解。

冒泡排序简介

冒泡排序是一种简单的排序算法。它的基本概念是通过反复比较相邻的元素，将较大的元素逐渐“冒泡”到数组的末尾。虽然冒泡排序的效率相对较低，尤其在处理大数据时，但它是算法教学中的经典例子，能够帮助我们理解排序的基本思想。

工作原理

冒泡排序的基本步骤如下：

1. 从数组的第一个元素开始，比较相邻的两个元素。
2. 如果前一个元素大于后一个元素，则交换这两个元素。
3. 重复步骤1和步骤2，直至数组末尾。
4. 针对每一个遍历，最大的元素将被“冒泡”到末尾。
5. 对剩余的部分重复以上步骤，直到整个数组有序。

在伪代码中，冒泡排序可以表示为：

for i from 0 to n-1:
    for j from 0 to n-i-1:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])

其中，n 是数组的长度，arr 是需要排序的数组。

实际案例

让我们通过一个具体的例子来演示冒泡排序的工作流程。

假设我们有一个数组：

arr = [64, 34, 25, 12, 22, 11, 90]

我们希望对这个数组进行升序排序。按照冒泡排序的算法步骤，我们将进行如下操作：

1. 第一轮：

   • 比较 64 和 34 → 交换，数组变为 [34, 64, 25, 12, 22, 11, 90]
   • 比较 64 和 25 → 交换，数组变为 [34, 25, 64, 12, 22, 11, 90]
   • 比较 64 和 12 → 交换，数组变为 [34, 25, 12, 64, 22, 11, 90]
   • 比较 64 和 22 → 交换，数组变为 [34, 25, 12, 22, 64, 11, 90]
   • 比较 64 和 11 → 交换，数组变为 [34, 25, 12, 22, 11, 64, 90]
   • 比较 64 和 90 → 不交换，保持不变。

   第一轮后，最大的元素 90 被放在了最后。

2. 第二轮：

   • 同样的过程，将未排序部分 [34, 25, 12, 22, 11, 64] 进行比较和交换。

经过几轮后，我们的数组将逐步变为：

[11, 12, 22, 25, 34, 64, 90]

代码实现

下面是使用 Python 编写的冒泡排序实现：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 在每一轮中，设置一个标志位
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # 交换
                swapped = True
        # 如果没有元素交换，说明数组已经有序
        if not swapped:
            break

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组:", arr)

在上述代码中，我们定义了一个函数 bubble_sort，输入是一个待排序的数组 arr。我们引入了一个标志位 swapped，以优化算法——如果在某一轮中没有进行任何交换，则说明数组已然有序，提前结束排序。

小结

在本篇中，我们实现了一个简单但经典的排序算法——冒泡排序。通过代码示例和具体案例，我们了解了该算法的工作机制和具体实现。冒泡排序适合小规模数据的排序学习，但在实际应用中，我们往往会使用更高效的排序算法。

在下一篇中，我们将介绍另一个常见的排序算法：选择排序，并进行更深入的分析与实现。希望通过这些系列教程，能够帮助算法小白们逐步掌握和应用基本的算法知识。