14 实现一个简单排序算法

在上一篇教程中，我们学习了算法分析的基础知识，特别是如何使用大O表示法来评价算法的时间复杂度和空间复杂度。今天，我们将继续进行实际的算法实践，具体实现一个简单的排序算法——冒泡排序。

冒泡排序概述

冒泡排序是一种简单的排序算法。它重复地遍历待排序的数组，比较相邻的元素，并在它们的顺序错误时交换它们。这个过程会一直进行，直到没有需要交换的元素为止。冒泡排序的名字来源于较小的元素“冒泡”到数组的顶端。

冒泡排序的基本步骤

1. 从数组的最左边开始，比较相邻的两个元素。
2. 如果前一个元素大于后一个元素，则交换它们。
3. 向右移动一个位置，重复步骤1和2，直到到达数组的末尾。
4. 经过一轮的比较，最大的元素会被“冒泡”到数组的末尾。
5. 忽略最后一个已经排序的元素，重复上述步骤，直到所有元素都排序完成。

冒泡排序的时间复杂度

冒泡排序的最坏和平均时间复杂度为 $O(n^2)$，其中 $n$ 是数组的长度。在最佳情况下（当数组已经是排好序的），时间复杂度为 $O(n)$。这是因为只需要遍历一遍，如果没有进行任何交换，就可以提前结束排序。

实现冒泡排序

下面是用 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
    return arr

# 测试冒泡排序
sample_array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(sample_array)
print("排序后的数组:", sorted_array)

代码解析

1. 通过 len(arr) 获取数组的长度，确定需要的遍历次数。
2. 外层循环用于控制排序的轮数；内层循环用于逐对比较相邻元素。
3. swapped 变量用于优化，当某一轮没有进行交换时，说明数组已经有序，可以提前结束排序过程。
4. 最后返回排序后的数组。

案例分析

让我们来分析一下上面的示例代码：

• 初始数组为 [64, 34, 25, 12, 22, 11, 90]。
• 第一轮比较后数组状态：
  • [34, 25, 12, 22, 11, 64, 90] （64与34交换）
  • [25, 12, 22, 11, 34, 64, 90] （34与25交换）
  • [12, 22, 11, 25, 34, 64, 90] （25与12交换）
  • [12, 11, 22, 25, 34, 64, 90] （22与11交换）
  • [11, 12, 22, 25, 34, 64, 90] （11与12交换）
  • 最后，90已经是最大的元素，所以下一轮比较会略过。

经过数轮的比较与交换，最终得到排序后的数组为 [11, 12, 22, 25, 34, 64, 90]。

结语

今天我们学习了冒泡排序这一基本的排序算法，通过简单的示例和代码实现，掌握了其基本思想和实现方式。冒泡排序简单易懂，但在大型数据集上效率较低，常常在实际应用中用更高效的排序算法替代。在下一篇文章中，我们将继续深入探索另一个简单的查找算法。

希望大家在实际编程中多多练习，熟悉排序算法的实现方式。