实验二：快速排序算法性能分析

本实验将通过 Python 代码实现快速排序算法，并生成不同规模的随机数数据集，测试快速排序算法在不同数据量下的性能表现，分析其时间复杂度和效率。

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 增大时，运行时间也会增大。