顺序查找,快速排序和折半查找的综合应用代码
时间: 2023-07-04 21:10:52 浏览: 49
以下是一个基于顺序查找、快速排序和折半查找的综合应用代码示例:
```python
# 定义顺序查找函数
def sequential_search(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i
return -1
# 定义快速排序函数
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[0]
left = [x for x in lst[1:] if x < pivot]
right = [x for x in lst[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# 定义折半查找函数
def binary_search(lst, key):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] < key:
low = mid + 1
elif lst[mid] > key:
high = mid - 1
else:
return mid
return -1
# 综合应用函数
def search(lst, key):
# 先进行快速排序
sorted_lst = quick_sort(lst)
# 再进行折半查找
index = binary_search(sorted_lst, key)
if index != -1:
return index
# 如果折半查找未找到,则进行顺序查找
return sequential_search(lst, key)
```
使用示例:
```python
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
key = 4
index = search(lst, key)
print(index) # 输出 3
```
注意,这只是一个简单的示例,实际应用中,需要根据具体情况进行代码的优化和改进。