1.二分查找
def binary_search(mylist, item):
low = 0
high = len(mylist)-1
while low <= high:
mid = (low + high)//2 # 如果(low + high)//2不是偶数，Python自动将mid向下圆整。
guess = mylist[mid]
if guess == item:
return mid
if guess > item: # 猜的数大了
high = mid - 1
else: # 猜的数小了
low = mid + 1
return None
my_list = [1, 3, 4, 5, 7, 9]
print(binary_search(my_list, 3))
大O 表示法指出了最糟情况下的运行时间.(除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。最糟情况和平均情况将在后面讨论)
这里顺带说一下简单查找法的算法运行时间为O(n),而二分查找法的运行时间为O(log n)
2.选择排序
def findSmallest(arr):
"""找出数组中最小元素的函数"""
smallest = arr[0] # 存储最小的值
smallest_index = 0 # 存储最小的值的索引
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
"""现在可以使用这个函数来编写选择排序算法了"""
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr) # 找出数组中最小的元素,并将其加入到新数组中
newArr.append(arr.pop(smallest))
return newArr
print(selectionSort([5, 3, 6, 2, 10]))
选择排序算法运行时间为O(n2)
3.快速排序
def quicksort(array):
if len(array) < 2:
return array # 基线条件：为空或只包含一个元素的数组是“有序”的
else:
pivot = array[0] # 递归条件
less = [i for i in array[1:] if i <= pivot] # 由所有小于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot] # 由所有大于基准值的元素组成的子数组
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
快速排序算法运行时间为O(nlog n)
注:何为平均情况，何为最糟情况呢? 快速排序的性能高度依赖于你选择的基准条件,快速排序算法最糟糕的情况下运行时间为O(n2),最佳情况为O(nlog n),最佳情况也是平均情况.只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。快速排序是最快的排序算法之一，也是D&C (divide and conquer)典范.
关于大O表示法,算法时间复杂度,可查看这个链接https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation
