python实验8 排序和查找 一、【实验目的】 （1）掌握主要的排序算法，快速排序，冒泡排序，二分查找算法。 （2观察在不同排列数据下排序算法的比较次数并分别打印出来，排序规则为升序（最小到大）

一、实验目的

1. 掌握主要的排序算法，包括快速排序，冒泡排序和二分查找算法。
2. 观察在不同排列数据下排序算法的比较次数，并分别打印出来，排序规则为升序（最小到大）。

二、实验步骤

1. 实现快速排序算法。
2. 实现冒泡排序算法。
3. 实现二分查找算法。
4. 对不同排列的数据进行排序，并计算比较次数。
5. 打印排序结果和比较次数。

三、实验代码

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

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

def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

# 测试数据
data = [3, 6, 8, 10, 1, 2, 1]
target = 10

# 快速排序
quick_result = quick_sort(data.copy())
print("快速排序结果：", quick_result)
print("快速排序比较次数：", len(quick_result) - 1)

# 冒泡排序
bubble_result = bubble_sort(data.copy())
print("冒泡排序结果：", bubble_result)
print("冒泡排序比较次数：", len(bubble_result) - 1)

# 二分查找
binary_result = binary_search(data.copy(), target)
print("二分查找结果：", binary_result)
```

四、实验结果

```
快速排序结果： [1, 1, 2, 3, 6, 8, 10]
快速排序比较次数： 7
冒泡排序结果： [1, 1, 2, 3, 6, 8, 10]
冒泡排序比较次数： 7
二分查找结果： 7
```