以待排序数组的大小n为输入规模,固定n,随机产生20组测试样本,统计不同排序算法在2
时间: 2023-05-13 18:02:51 浏览: 81
首先,需要明确的是不同的排序算法在不同的数据规模下表现是不同的。因此,本问题中假定了待排序数组的大小n为输入规模。
接下来,需要产生20组测试样本。可以使用Python代码进行实现,如下所示:
```python
import random
samples = []
n = 1000 # 假设待排序数组大小为1000
for i in range(20):
sample = [random.randint(1, 1000) for j in range(n)]
samples.append(sample)
```
上述代码中,生成了20组大小为1000的随机样本。
接下来需要分别对这些样本进行排序,并统计排序算法的运行时间。常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等,这里选择其中的四个进行实现。
下面是各个排序算法的Python代码实现:
```python
# 冒泡排序
def bubble_sort(lst):
n = len(lst)
for i in range(n):
for j in range(n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
# 插入排序
def insertion_sort(lst):
n = len(lst)
for i in range(1, n):
key = lst[i]
j = i - 1
while j >= 0 and lst[j] > key:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
return lst
# 选择排序
def selection_sort(lst):
n = len(lst)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if lst[j] < lst[min_idx]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst
# 快速排序
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[0]
left_lst = [x for x in lst[1:] if x <= pivot]
right_lst = [x for x in lst[1:] if x > pivot]
return quick_sort(left_lst) + [pivot] + quick_sort(right_lst)
```
接下来可以编写测试函数来测试每种排序算法在每个样本上的运行时间,如下所示:
```python
import time
def test(func):
total_time = 0
for sample in samples:
start_time = time.time()
sorted_lst = func(sample)
end_time = time.time()
total_time += (end_time - start_time)
return total_time / 20 # 返回平均时间
```
最后,可以调用测试函数对所有排序算法进行测试,并输出结果,如下所示:
```python
bubble_sort_time = test(bubble_sort)
insertion_sort_time = test(insertion_sort)
selection_sort_time = test(selection_sort)
quick_sort_time = test(quick_sort)
print('冒泡排序平均时间:', bubble_sort_time)
print('插入排序平均时间:', insertion_sort_time)
print('选择排序平均时间:', selection_sort_time)
print('快速排序平均时间:', quick_sort_time)
```
这样就可以统计不同排序算法在待排序数组大小为n、随机产生的20组测试样本上的运行时间了。通过比较运行时间,可以得到哪种排序算法更加高效。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)