每日一练：冒泡排序

1. 概述

  冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。
  冒泡排序过程：

1. 从第一个元素开始，依次比较相邻的两个元素。
2. 如果顺序不对（升序时前面的元素比后面的元素大，降序时前面的元素比后面的元素小），则交换它们的位置。
3. 继续向后比较和交换，直到最后一个元素。
4. 一次遍历完成后，最大（或最小）的元素就会被移动到最后一个位置。
5. 重复以上步骤，每次遍历都将未排序序列中的最大（或最小）元素移动到正确的位置。
6. 重复这个过程，直到整个序列有序。

  如下图所示：

2. 代码实现

  下面三个示例展示了冒泡排序在不同情况下的应用。冒泡排序的时间复杂度为O(n^2)，在实际应用中，对大型数据集的排序不够高效，但它是一种容易理解和实现的排序算法。

2.1 升序排序

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # 最后i个元素已经排好序，无需再比较
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换元素
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 示例
arr1 = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr1)
print("升序排序结果:", arr1)

2.2 降序排序

def bubble_sort_desc(arr):
    n = len(arr)
    
    for i in range(n):
        # 最后i个元素已经排好序，无需再比较
        for j in range(0, n-i-1):
            if arr[j] < arr[j+1]:
                # 交换元素
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 示例
arr2 = [64, 34, 25, 12, 22, 11, 90]
bubble_sort_desc(arr2)
print("降序排序结果:", arr2)

2.3 字符串排序

def bubble_sort_str(arr):
    n = len(arr)
    
    for i in range(n):
        # 最后i个元素已经排好序，无需再比较
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换元素
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 示例
arr3 = ["apple", "banana", "orange", "grape", "kiwi"]
bubble_sort_str(arr3)
print("字符串列表排序结果:", arr3)

3. 参考

代码007普通

打赏 收藏 海报 链接