实验二 快速排序

1.测试数据集的生成 为了生成测试数据集，我们可以使用Python的random模块来生成随机数。具体实现可以参考以下代码：

import random

def generate_random_array(length): """ 生成指定长度的随机整数数组 """ return [random.randint(0, 1000) for _ in range(length)]

生成长度分别为100、1000、10000、100000的随机整数数组

array_100 = generate_random_array(100) array_1000 = generate_random_array(1000) array_10000 = generate_random_array(10000) array_100000 = generate_random_array(100000)

2.快速排序算法的实现 快速排序是一种常用的排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后再对这两部分分别进行快速排序，以达到整个序列有序的目的。具体实现可以参考以下代码：

def quick_sort(array): """ 快速排序算法 """ if len(array) <= 1: return array pivot = array[0] left = [] right = [] for i in range(1, len(array)): if array[i] < pivot: left.append(array[i]) else: right.append(array[i]) return quick_sort(left) + [pivot] + quick_sort(right)

3.快速排序算法在测试集上的性能分析 为了测试快速排序算法在不同数据规模下的性能，我们可以使用Python的time模块来计时。具体实现可以参考以下代码：

import time

def test_quick_sort(array, array_name): """ 测试快速排序算法在指定数据集上的性能 """ start_time = time.time() sorted_array = quick_sort(array) end_time = time.time() print(f"{array_name} sorted in {end_time - start_time:.6f}s")

test_quick_sort(array_100, "array_100") test_quick_sort(array_1000, "array_1000") test_quick_sort(array_10000, "array_10000") test_quick_sort(array_100000, "array_100000")

以上代码中，我们使用了time.time()函数来获取当前时间戳，然后计算排序所用时间。运行代码后，我们可以得到类似以下的输出结果：

array_100 sorted in 0.000003s array_1000 sorted in 0.000119s array_10000 sorted in 0.002290s array_100000 sorted in 0.026209s

从结果可以看出，随着数据规模的增大，快速排序算法的运行时间也随之增大。这是因为快速排序算法的时间复杂度为O(nlogn)，其中n为待排序元素的个数，所以当n增大时，运行时间也会增大