当前位置：首页 > article >正文

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

article 2024/12/26 10:43:28

一、实验目的

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

二、实验内容

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

三、实验演示

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 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)


# 复制 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 time

random_list = [random.randint(1, 100) for _ in range(20)]
print("列表:", random_list)


def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1


merge_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, "秒")

冒泡排序实验结果截图：