查找：
- 順序查找
- 二分查找（折半查找）
- 二叉排序樹查找
- 哈希查找，時間復雜度O(1)
- Fibonacci查找，時間復雜度O(logN)
- 分塊查找槐瑞，時間復雜度O(logN+N/m)
排序：
- 冒泡排序
- 快速排序
- 歸并排序
- 插入排序
- 選擇排序
查找：
順序查找嫌拣，時間復雜度O(N)
nums = [4,7,12,20,36,48,50,77,90]
n = 36
for i in nums:
if(i == n):
print(i)
break
#輸出36
折半查找（其實就是二分查找）時間復雜度O(logN)
#二分查找,給定一個數字n，給定一個有序列表孝宗，找到數字n的下標，否則返回-1
def searchNum(n,list):
low=0
high=(len(list))
while low<=high:
mid = (low + high)//2
if n>list[mid]:
low=mid+1
elif n<list[mid]:
high=mid-1
else:
return mid
return -1
list=[1,4,6,9,12,45,78,900,1212];
mid=searchNum(45,list)
print(mid)
二叉排序樹的查找
# 二叉樹查找 Python實現
class BSTNode:
"""
定義一個二叉樹節(jié)點類耕肩。
以討論算法為主因妇，忽略了一些諸如對數據類型進行判斷的問題。
"""
def __init__(self, data, left=None, right=None):
"""
初始化
:param data: 節(jié)點儲存的數據
:param left: 節(jié)點左子樹
:param right: 節(jié)點右子樹
"""
self.data = data
self.left = left
self.right = right
class BinarySortTree:
"""
基于BSTNode類的二叉查找樹猿诸。維護一個根節(jié)點的指針婚被。
"""
def __init__(self):
self._root = None
def is_empty(self):
return self._root is None
def search(self, key):
"""
關鍵碼檢索
:param key: 關鍵碼
:return: 查詢節(jié)點或None
"""
bt = self._root
while bt:
entry = bt.data
if key < entry:
bt = bt.left
elif key > entry:
bt = bt.right
else:
return entry
return None
def insert(self, key):
"""
插入操作
:param key:關鍵碼
:return: 布爾值
"""
bt = self._root
if not bt:
self._root = BSTNode(key)
return
while True:
entry = bt.data
if key < entry:
if bt.left is None:
bt.left = BSTNode(key)
return
bt = bt.left
elif key > entry:
if bt.right is None:
bt.right = BSTNode(key)
return
bt = bt.right
else:
bt.data = key
return
def delete(self, key):
"""
二叉查找樹最復雜的方法
:param key: 關鍵碼
:return: 布爾值
"""
p, q = None, self._root # 維持p為q的父節(jié)點，用于后面的鏈接操作
if not q:
print("空樹梳虽！")
return
while q and q.data != key:
p = q
if key < q.data:
q = q.left
else:
q = q.right
if not q: # 當樹中沒有關鍵碼key時址芯，結束退出。
return
# 上面已將找到了要刪除的節(jié)點窜觉，用q引用谷炸。而p則是q的父節(jié)點或者None（q為根節(jié)點時）。
if not q.left:
if p is None:
self._root = q.right
elif q is p.left:
p.left = q.right
else:
p.right = q.right
return
# 查找節(jié)點q的左子樹的最右節(jié)點禀挫，將q的右子樹鏈接為該節(jié)點的右子樹
# 該方法可能會增大樹的深度淑廊，效率并不算高√嘏兀可以設計其它的方法季惩。
r = q.left
while r.right:
r = r.right
r.right = q.right
if p is None:
self._root = q.left
elif p.left is q:
p.left = q.left
else:
p.right = q.left
def __iter__(self):
"""
實現二叉樹的中序遍歷算法,
展示我們創(chuàng)建的二叉查找樹.
直接使用python內置的列表作為一個棧。
:return: data
"""
stack = []
node = self._root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
yield node.data
node = node.right
if __name__ == '__main__':
lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]
bs_tree = BinarySortTree()
for i in range(len(lis)):
bs_tree.insert(lis[i])
# bs_tree.insert(100)
bs_tree.delete(58)
for i in bs_tree:
print(i, end=" ")
# print("\n", bs_tree.search(4))
哈希查找腻格，時間復雜度O(1)
分塊查找画拾，時間復雜度O(logN+N/m)
將列表分塊，找出最大值
先找最大值再順序查找
Fibonacci查找菜职，時間復雜度O(logN)
MAXSIZE = 20
#構建一個febonacci列表
def fibonacci(): # 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
f = [0] * MAXSIZE
f[0] = 1
f[1] = 1
for i in range(2, MAXSIZE):
f[i] = f[i-1] + f[i-2]
return f
#搜索
def fibonacciSearch(array, value):
low, mid, high = 0, 0, len(array)-1
k = 0
f = fibonacci()
#找到比給定數組大小的最小菲波那切數
while len(array) > f[k]-1:
k += 1
#將數組的長度補到fk-1的大大小青抛，數值為原列表最后的數值
temp = array + [array[-1] * (f[k]-1-len(array))]
while low <= high:
mid = low + f[k-1] - 1
if temp[mid] > value:
high = mid - 1
k = k - 1
elif temp[mid] < value:
low = mid + 1
k = k - 2
else:
if mid <= high: # 如果在high位前，則返回mid位置酬核，否則返回high位置
return mid
else:
return high
return -1
if __name__ == '__main__':
a = [1, 3, 5, 6, 7, 88]
print(fibonacciSearch(a, 2))
差值查找蜜另，時間復雜度O(log(logN))
通過類比，我們可以將二分查找的點改進為如下：
mid=low+(high-low)*(key-a[low])/(a[high]-a[low])//(1/2)
換為(key-a[low])/(a[high]-a[low])
也就是將上述的比例參數1/2改進為自適應的嫡意，根據關鍵字在整個有序表中所處的位置举瑰，讓mid值的變化更靠近關鍵字key，這樣也就間接地減少了比較次數蔬螟。
排序
插入排序
#插入排序
# python
def insert_sort(data,dataSorted):
if len(data)<1:
return dataSorted
temp=data.pop(0)
if len(dataSorted)<1:
dataSorted.append(temp)
return insert_sort(data,dataSorted)
i=0
while temp<dataSorted[i]:
if i == len(dataSorted) - 1:
break
i+=1
dataSorted.insert(i,temp)
print(dataSorted)
return insert_sort(data,dataSorted)
array=[1,3,7,4,3,2,6,8,4,2]
print(insert_sort(array,[]))
冒泡排序
def bubbleSort(arr):
n = len(arr)
# 遍歷所有數組元素
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("排序后的數組:")
for i in range(len(arr)):
print ("%d" %arr[i]),
快速排序
#快速排序
def sortQuckily(array):
if len(array)<2:
return array
else:
axis=array[0]
less=[i for i in array[1:] if i<axis]
greater=[i for i in array[1:] if i>axis]
return sortQuckily(less)+[axis]+sortQuckily(greater)
kinoList=[1,4,6,3,98,4,33,67,1,4,0,6,3,78]
print(sortQuckily(kinoList))
我個人覺得這是快排最漂亮的代碼了
歸并排序
#先實現拆分
def cut(array):
if len(array)<=1:
print(array)
return array
mid=len(array)//2
print(mid)
left=cut(array[0:mid])
right=cut(array[mid:len(array)])
return megret(left,right)
def megret(left,right):
result=[]
i,j=0,0
while len(left)>i and len(right)>j:
if left[i]>right[j]:
result.append(right[j])
j+=1
else:
result.append(left[i])
i+=1
result.extend(left[i:])
result.extend(right[j:])
return result
array=[3,64,2]
print(cut(array))
選擇排序
#選擇排序
def chooseSort(listKino):
smallest=listKino[0]
index=0
for i in range(1,len(listKino)):
if(listKino[i]<smallest):
smallest=listKino[i]
index=i
temp=listKino[index]
del listKino[index]
return temp
listKino=[1,3,9456,445,5,7,2,23232,34343,45,67,45454,4,12,89,112,778,3,2323,7845,9001,12121,90901]
listNew=[]
for i in range(len(listKino)):
listNew.append(chooseSort(listKino))
print(listNew)
屏幕快照 2019-09-18 下午1.40.09.png
