Python 冒泡排序
最后修改于 2025年3月8日
在本文中，我们将解释 Python 中的冒泡排序算法。我们涵盖了按升序和降序对数字和文本数据进行排序。我们还将比较冒泡排序和快速排序，并进行基准测试。
算法 是解决问题或执行计算的分步过程。算法是计算机科学和编程的基础。
排序 是将数据按特定顺序（例如升序或降序）排列的过程。排序是编程中的一个常见操作，并在各种应用程序中使用。
常用排序算法
一些常见的排序算法包括
- 气泡排序
- 快速排序
- 归并排序
- 插入排序
- 选择排序
气泡排序算法
冒泡排序是一种简单的排序算法，它重复地遍历列表，比较相邻的元素，并在它们顺序不当时交换它们。对列表的遍历会重复进行，直到列表被排序。
气泡排序示例
以下是冒泡排序算法的 Python 实现。
bubble_sort.py
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]
# Example usage
nums = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(nums)
print("Sorted array:", nums)
该示例使用冒泡排序对数字列表进行升序排序。
$ ./bubble_sort.py Sorted array: [11, 12, 22, 25, 34, 64, 90]
对文本数据进行排序
冒泡排序也可用于对文本数据进行排序。以下示例按升序和降序对字符串列表进行排序。
bubble_sort_text.py
def bubble_sort(arr, reverse=False):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if (arr[j] > arr[j+1] and not reverse) or (arr[j] < arr[j+1] and reverse):
arr[j], arr[j+1] = arr[j+1], arr[j]
# Example usage
words = ["banana", "apple", "cherry", "date"]
bubble_sort(words)
print("Sorted in ascending order:", words)
bubble_sort(words, reverse=True)
print("Sorted in descending order:", words)
该示例按升序和降序对单词列表进行排序。
$ ./bubble_sort_text.py Sorted in ascending order: ['apple', 'banana', 'cherry', 'date'] Sorted in descending order: ['date', 'cherry', 'banana', 'apple']
比较气泡排序与快速排序
冒泡排序简单但对于大型数据集效率低下。快速排序更有效且被广泛使用。以下示例比较了冒泡排序和快速排序的性能。
sort_benchmark.py
import time
import random
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]
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Generate a large list of random numbers
data = [random.randint(0, 1000) for _ in range(1000)]
# Benchmark Bubble Sort
start_time = time.time()
bubble_sort(data.copy())
bubble_time = time.time() - start_time
# Benchmark Quick Sort
start_time = time.time()
quick_sort(data.copy())
quick_time = time.time() - start_time
print(f"Bubble Sort time: {bubble_time:.6f} seconds")
print(f"Quick Sort time: {quick_time:.6f} seconds")
该示例对 1000 个随机数列表上的冒泡排序和快速排序进行基准测试。
冒泡排序是一种简单的排序算法，但对于大型数据集效率低下。快速排序更有效，并且是实际应用的首选。理解排序算法对于编写高效程序至关重要。
来源
在本文中，我们解释了 Python 中的冒泡排序算法。
作者
列出所有 Python 教程。