1.二分查找
def binary_search(mylist, item):
low = 0
high = len(mylist)-1
while low <= high:
mid = (low + high)//2 # 如果(low + high)//2不是偶數(shù)褪迟，Python自動(dòng)將mid向下圓整。
guess = mylist[mid]
if guess == item:
return mid
if guess > item: # 猜的數(shù)大了
high = mid - 1
else: # 猜的數(shù)小了
low = mid + 1
return None
my_list = [1, 3, 4, 5, 7, 9]
print(binary_search(my_list, 3))
大O 表示法指出了最糟情況下的運(yùn)行時(shí)間.(除最糟情況下的運(yùn)行時(shí)間外，還應(yīng)考慮平均情況的運(yùn)行時(shí)間城榛，這很重要土童。最糟情況和平均情況將在后面討論)
這里順帶說一下簡(jiǎn)單查找法的算法運(yùn)行時(shí)間為O(n),而二分查找法的運(yùn)行時(shí)間為O(log n)
2.選擇排序
def findSmallest(arr):
"""找出數(shù)組中最小元素的函數(shù)"""
smallest = arr[0] # 存儲(chǔ)最小的值
smallest_index = 0 # 存儲(chǔ)最小的值的索引
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
"""現(xiàn)在可以使用這個(gè)函數(shù)來編寫選擇排序算法了"""
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr) # 找出數(shù)組中最小的元素,并將其加入到新數(shù)組中
newArr.append(arr.pop(smallest))
return newArr
print(selectionSort([5, 3, 6, 2, 10]))
選擇排序算法運(yùn)行時(shí)間為O(n2)
3.快速排序
def quicksort(array):
if len(array) < 2:
return array # 基線條件：為空或只包含一個(gè)元素的數(shù)組是“有序”的
else:
pivot = array[0] # 遞歸條件
less = [i for i in array[1:] if i <= pivot] # 由所有小于基準(zhǔn)值的元素組成的子數(shù)組
greater = [i for i in array[1:] if i > pivot] # 由所有大于基準(zhǔn)值的元素組成的子數(shù)組
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
快速排序算法運(yùn)行時(shí)間為O(nlog n)
注:何為平均情況，何為最糟情況呢? 快速排序的性能高度依賴于你選擇的基準(zhǔn)條件,快速排序算法最糟糕的情況下運(yùn)行時(shí)間為O(n2),最佳情況為O(nlog n),最佳情況也是平均情況.只要你每次都隨機(jī)地選擇一個(gè)數(shù)組元素作為基準(zhǔn)值，快速排序的平均運(yùn)行時(shí)間就將為O(n log n)阱驾。快速排序是最快的排序算法之一，也是D&C (divide and conquer)典范.
關(guān)于大O表示法,算法時(shí)間復(fù)雜度,可查看這個(gè)鏈接https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation
