python实现快速排序和冒泡排序比较

需求

python实现快速排序和冒泡排序比较，并统计两种算法所需的时间

实现效果

代码实现

import random
import timedef quick_sort(arr):"""快速排序算法的实现。参数:arr (list): 需要排序的列表返回:list: 排序后的列表"""if len(arr) <= 1:return arrelse:pivot = arr[0]less = [x for x in arr[1:] if x <= pivot]greater = [x for x in arr[1:] if x > pivot]return quick_sort(less) + [pivot] + quick_sort(greater)def bubble_sort(arr):"""冒泡排序算法的实现。参数:arr (list): 需要排序的列表返回:list: 排序后的列表"""n = len(arr)for i in range(n):swapped = Falsefor j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arrdef measure_time(sort_func, arr):"""测量排序算法的执行时间。参数:sort_func (function): 排序函数arr (list): 需要排序的列表返回:tuple: (排序后的列表, 执行时间)"""start_time = time.time()sorted_arr = sort_func(arr.copy())end_time = time.time()elapsed_time = end_time - start_timereturn sorted_arr, elapsed_timeif __name__ == "__main__":# 生成一个包含 10000 个随机数的列表unsorted_list = [random.randint(1, 100000) for _ in range(10000)]# 测试快速排序sorted_list_quick, time_quick = measure_time(quick_sort, unsorted_list)print(f"快速排序结果: {sorted_list_quick}")print(f"快速排序时间: {time_quick:.10f} 秒")# 测试冒泡排序sorted_list_bubble, time_bubble = measure_time(bubble_sort, unsorted_list)print(f"冒泡排序结果: {sorted_list_bubble}")print(f"冒泡排序时间: {time_bubble:.10f} 秒")

代码说明

1. 导入模块：

   import time
   import random

   • time 模块用于测量时间。
   • random 模块用于生成随机数。

2. 快速排序函数：

   def quick_sort(arr):if len(arr) <= 1:return arrelse:pivot = arr[0]less = [x for x in arr[1:] if x <= pivot]greater = [x for x in arr[1:] if x > pivot]return quick_sort(less) + [pivot] + quick_sort(greater)

   • 快速排序的基本实现，使用递归方法。

3. 冒泡排序函数：

   def bubble_sort(arr):n = len(arr)for i in range(n):swapped = Falsefor j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr

   • 冒泡排序的基本实现，使用嵌套循环比较并交换相邻元素。

4. 测量时间函数：

   def measure_time(sort_func, arr):start_time = time.time()sorted_arr = sort_func(arr.copy())end_time = time.time()elapsed_time = end_time - start_timereturn sorted_arr, elapsed_time

   • measure_time 函数接受一个排序函数和一个列表，测量排序函数的执行时间，并返回排序后的列表和执行时间。