查找：
- 顺序查找
- 二分查找（折半查找）
- 二叉排序树查找
- 哈希查找，时间复杂度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:
"""
定义一个二叉树节点类。
以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。
"""
def __init__(self, data, left=None, right=None):
"""
初始化
:param data: 节点储存的数据
:param left: 节点左子树
:param right: 节点右子树
"""
self.data = data
self.left = left
self.right = right
class BinarySortTree:
"""
基于BSTNode类的二叉查找树。维护一个根节点的指针。
"""
def __init__(self):
self._root = None
def is_empty(self):
return self._root is None
def search(self, key):
"""
关键码检索
:param key: 关键码
:return: 查询节点或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的父节点，用于后面的链接操作
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
# 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。
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
# 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树
# 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。
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):
"""
实现二叉树的中序遍历算法,
展示我们创建的二叉查找树.
直接使用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
