折半查找和快速排序的算法
时间: 2024-01-07 14:22:40 浏览: 167
折半查找和快速排序是常见的算法,下面是它们的介绍和示例代码:
1. 折半查找(Binary Search):
折半查找是一种在有序数组中查找指定元素的算法。它通过将数组分成两半,并与目标元素进行比较来确定目标元素的位置。如果目标元素小于中间元素,则在左半部分继续查找;如果目标元素大于中间元素,则在右半部分继续查找;如果目标元素等于中间元素,则找到了目标元素。
示例代码:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# 测试
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
print("Target found at index:", result) # 输出:Target found at index: 2
```
2. 快速排序(Quick Sort):
快速排序是一种常用的排序算法,它通过选择一个基准元素,将数组分成两部分,一部分小于基准元素,一部分大于基准元素,然后对这两部分递归地进行排序。
示例代码:
```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)
# 测试
arr = [5, 3, 9, 1, 7]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr) # 输出:Sorted array: [1, 3, 5, 7, 9]
```
阅读全文