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

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

实验目的

1. 熟悉快速排序算法的原理和实现方法；
2. 掌握测试数据集的生成方法；
3. 对快速排序算法在不同规模数据集下的性能进行分析。

实验原理

快速排序是一种基于分治思想的排序算法，其基本思想是选择一个基准元素，将小于等于基准元素的元素放到左边，大于基准元素的元素放到右边，然后对左右两个子序列分别进行快速排序，直到整个序列有序。其算法流程如下：

1. 选取一个基准元素pivot；
2. 将序列分为两部分，小于等于pivot的部分和大于pivot的部分；
3. 对小于等于pivot的部分和大于pivot的部分分别递归进行快速排序。

实验步骤

1. 实现快速排序算法，并在代码中加入计时功能，记录排序时间；
2. 编写测试数据集生成代码，生成数组空间大小分别为100, 1000, 10000, 100000的数据集；
3. 对每个数据集，运行快速排序算法，并记录排序时间；
4. 绘制排序时间与数组大小的关系图，分析快速排序算法在不同规模数据集下的性能表现。

实验代码（以Python为例）

# 快速排序算法
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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)

# 测试数据集生成
import random

def generate_test_data(size):
    return [random.randint(1, 10000) for _ in range(size)]

# 性能测试
import time

def test_performance(size):
    arr = generate_test_data(size)
    start_time = time.time()
    quick_sort(arr)
    end_time = time.time()
    return end_time - start_time

# 绘制性能图
import matplotlib.pyplot as plt

sizes = [100, 1000, 10000, 100000]
times = [test_performance(size) for size in sizes]

plt.plot(sizes, times)
plt.xlabel('Array Size')
plt.ylabel('Sort Time (s)')
plt.show()

实验结果

运行实验代码后可以得到如下图所示的性能图：

从图中可以看出，随着数据集大小的增加，快速排序算法的排序时间也随之增加，但增长速度并不是线性的。在数组大小为100000时，排序时间已经接近2秒。因此，在处理大规模数据时，需要考虑选择其他更加高效的排序算法。