PyCharm专业实验2 查找算法实现与比较

一、实验目的

        本文的实验目的是对随机生成的含20个元素的列表使用至少三种不同的排序算法进行排序，并通过事前和事后的性能分析来比较这些算法的效率。

二、实验内容

1. 数据准备：
   • 随机生成一个包含20个元素的列表，元素值在1到100之间。
2. 排序算法实现：
   • 实现冒泡排序算法，对列表进行排序。
   • 实现快速排序算法，对列表进行排序。
   • 实现归并排序算法，对列表进行排序。
3. 性能分析：
   • 事前性能分析：分析每种排序算法的时间复杂度和空间复杂度。
   • 事后性能分析：统计并记录每种排序算法的实际运行时间，通过比较来评估算法的效率。

三、实验演示

        1.随机生成一个含有20个元素的列表&实验截图

随机生成一个含20个元素的列表
import random
random_list = [random.randint(1, 100) for _ in range(20)]
print("列表:", random_list)

        2.使用至少3种算法对上述数据进行排序

#冒泡排序：
import random
from time import perf_counter  # 正确的导入方式random_list = [random.randint(1, 100) for _ in range(20)]
print("列表:", random_list)def bubble(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]bubble_list = random_list[:]start_time = perf_counter()  # 使用 perf_counter
bubble(bubble_list)  # 注意这里应该传递 bubble_list 而不是 random_list[:]
end_time = perf_counter()
print("排序:", bubble_list)
print("耗时:", end_time - start_time, "秒")##########################################################################################快速：
import random
from time import perf_counter# 重新生成或定义 random_list
random_list = [random.randint(1, 100) for _ in range(20)]
print("列表:", random_list)def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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)# 复制 random_list 到 quick_sort_list
quick_sort_list = random_list[:]start_time = perf_counter()
# 对 quick_sort_list 进行排序
sorted_list = quick_sort(quick_sort_list)
end_time = perf_counter()# 打印排序后的列表和耗时
print("排序:", sorted_list)
print("耗时:", end_time - start_time, "秒")##########################################################################################归并
import random
import timerandom_list = [random.randint(1, 100) for _ in range(20)]
print("列表:", random_list)def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1merge_sort_list = random_list[:]
start_time = time.perf_counter()
merge_sort(merge_sort_list)  # 直接对 merge_sort_list 进行排序
end_time = time.perf_counter()
print("排序:", merge_sort_list)  # 打印排序后的 merge_sort_list
print("耗时:", end_time - start_time, "秒")

冒泡排序实验结果截图：

快进排序实验结果截图：

归并排序实验结果截图：