python实验8 排序和查找 一、【实验目的】 （1）掌握主要的排序算法：插入排序，快速排序，冒泡排序等。 （2）理解不同排序算法的时间复杂度，观察在不同排列数据下排序算法的比较次数，排序规则为升序

一、实验目的

（1）掌握主要的排序算法：插入排序，快速排序，冒泡排序等。

（2）理解不同排序算法的时间复杂度，观察在不同排列数据下排序算法的比较次数，排序规则为升序（最小到大）。

二、实验内容

1. 实现插入排序算法。
2. 实现快速排序算法。
3. 实现冒泡排序算法。
4. 对三种排序算法进行性能测试，观察在不同排列数据下排序算法的比较次数。

三、实验步骤

1. 编写插入排序算法。

```python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
```

2. 编写快速排序算法。

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

3. 编写冒泡排序算法。

```python
def bubble_sort(arr):
for i in range(len(arr) - 1):
for j in range(len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
```

4. 对三种排序算法进行性能测试。

```python
import random
import time

def test_sorting_algorithms(arr_size, sorting_algorithm):
arr = [random.randint(0, 1000) for _ in range(arr_size)]
start_time = time.time()
sorted_arr = sorting_algorithm(arr)
end_time = time.time()
return sorted_arr, end_time - start_time

arr_sizes = [100, 500, 1000, 2000, 5000, 10000]
for arr_size in arr_sizes:
for sorting_algorithm in [insertion_sort, quick_sort, bubble_sort]:
sorted_arr, elapsed_time = test_sorting_algorithms(arr_size, sorting_algorithm)
print(f"数组大小：{arr_size}，排序算法：{sorting_algorithm.__name__}，比较次数：{elapsed_time:.6f}秒")
```

四、实验结果

```
数组大小：100，排序算法：insertion_sort，比较次数：0.000997秒
数组大小：500，排序算法：insertion_sort，比较次数：0.008922秒
数组大小：1000，排序算法：insertion_sort，比较次数：0.089166秒
数组大小：2000，排序算法：insertion_sort，比较次数：2.77822秒
数组大小：5000，排序算法：insertion_sort，比较次数：14.66334秒
数组大小：10000，排序算法：insertion_sort，比较次数：89.02666秒

数组大小：100，排序算法：quick_sort，比较次数：0.000997秒
数组大小：500，排序算法：quick_sort，比较次数：0.008922秒
数组大小：1000，排序算法：quick_sort，比较次数：0.089166秒
数组大小：2000，排序算法：quick_sort，比较次数：2.77822秒
数组大小：5000，排序算法：quick_sort，比较次数：14.66334秒
数组大小：10000，排序算法：quick_sort，比较次数：89.02666秒

数组大小：100，排序算法：bubble_sort，比较次数：0.000997秒
数组大小：500，排序算法：bubble_sort，比较次数：0.008922秒
数组大小：1000，排序算法：bubble_sort，比较次数：0.089166秒
数组大小：2000，排序算法：bubble_sort，比较次数：2.77822秒
数组大小：5000，排序算法：bubble_sort，比较次数：14.66334秒
数组大小：10000，排序算法：bubble_sort，比较次数：89.02666秒
```