排序
冒泡算法
arr = [1, 36, 7, 102, 54]
def bubblesort(arr):
n = len(arr)
for i in range(0,n-1): #最后一位不用排了，所以是n-1
for j in range(0,n-1-i): #冒泡排序从后到前，不断减少范围
if arr[j]>arr[j 1]:
arr[j],arr[j 1]=arr[j 1],arr[j]
return arr
bubblesort(arr)
print(arr)
arr = [1, 36, 7, 102, 54]
# 扫描一遍，把最小的放在最小位置
def selectsort(arr):
n = len(arr)
for i in range(0,n-1):
min_index = i #记录每一个位子
for j in range(i 1,n):
if arr[i] > arr[j]:
min_index = j
arr[i],arr[min_index] = arr[min_index],arr[i]
return arr
selectsort(arr)
print(arr)
arr = [1, 36, 7, 102, 54]
def insertionsort(arr):
n = len(arr)
for i in range(1, n):
j = i - 1 # i是当前位， j是前一位
while j >= 0:
if arr[j] > arr[i]: # 前面一位大于后面一位
tem = arr[i]
arr[j 1] = arr[j]
arr[j] = tem
j -= 1
return (arr)
归并排序
def merge_sort(s):
n = len(s)
if n < 2:
return s
mid = n // 2
s1 = s[0:mid]
s2 = s[mid:n]
merge_sort(s1)
merge_sort(s2)
merge(s1, s2, s)
def merge(s1, s2, s):
i = j = 0
while i j < len(s):
if j == len(s2) or (i < len(s1) and s1[i] < s2[j]):
s[i j] = s1[i]
i = 1
else:
s[i j] = s2[j]
i = 1
return s
链表归并排序
class linkedqueue():
def __init__(self, val):
self.val = val
self.next = none
def enqueue(self):
pass
def dequeue(self):
pass
class solution:
s = linkedqueue(none)
def merge(self, s1, s2, s):
while not s1.is_empty() and s2.is_empty():
if s1.first() < s2.first():
s.enqueue(s1.dequeue())
else:
s.enqueue(s2.dequeue())
while not s1.is_empty():
s.enqueue(s1.dequeue())
while not s2.is_empty():
s.enqueue(s2.dequeue())
def merge_sort(self, s):
n = len(s)
if n < 2:
return
s1 = linkedqueue(none)
s2 = linkedqueue(none)
while len(s1) < n//2:
s1.enqueue(s.dequeue())
while not s.is_empty():
s2.enqueue(s.dequeue())
self.merge_sort(s1)
self.merge_sort(s2)
class solution:
def quicksort(self, s):
if len(s) < 2:
return s
else:
pivot = s[len(s)//2] # 基准值
left = [i for i in s if i < pivot]
right = [i for i in s if i > pivot]
mid = [i for i in s if i == pivot]
return self.quicksort(left) mid self.quicksort(right)
if __name__ == '__main__':
arr = [57, 89, 65, 4, 5, 7, 32, 28, 456]
solution = solution()
print(solution.quicksort(arr))
原地快速排序
def inplace_quick_sort(s, a, b):
if a >= b: return
pivot = s[b]
left = a
right = b-1
while left <= right:
while left <= right and s[left] < pivot:
left = 1
while left <= right and pivot < s[right]:
right -= 1
if left <= right:
s[left], s[right] = s[right], s[left]
left, right = left 1, right-1
s[left], s[b] = s[b], s[left]
inplace_quick_sort(s, a, left-1)
inplace_quick_sort(s, left 1, b)
return s
s = [1, 8, 6, 5, 7, 2]
print(inplace_quick_sort(s, 0, 5))
import random
source = [random.randrange(10000 i) for i in range(10000)]
step = int(len(source)/2)
while step>0:
for index in range(0, len(source)):
if index step < len(source):
current_val = source[index]
if current_val > source[index step]:
source[index], source[index step] = source[index step], source[index]
step = int(step/2)
else:
for index in range(1, len(source)):
current_val = source[index]
position = index
while position > 0 and source[position-1] > current_val:
source[position] = current_val
print(source)
import random
def radixsort():
a = [random.randint(1, 9999) for i in range(10000)]
for k in range(4): # 4轮排序
s = [[] for i in range(10)] # 10个桶
for i in a:
s[i // (10 ** k) % 10].append(i)
a = [a for b in s for a in b]
return a
print(radixsort())
堆排序
def max_heapify(heap, heapsize, root):
'''
对一个父节点及其左右孩子节点调整；heap：list；heapsize：做数组最大限制，root:根节点位置
'''
left = 2 * root 1 # 注意此处下标从0开始，下标为1开始时，公式为left = 2*root
right = left 1
large = root
if left < heapsize and heap[large] < heap[left]:
large = left
if right < heapsize and heap[large] < heap[right]:
large = right
if root != large:
heap[root], heap[large] = heap[large], heap[root]
# 堆建立过程自下而上调整每个父节点及左右孩子
def build_heap(heap, heapsize):
for root in range((heapsize - 1) // 2, -1, -1): # 表示求每个父节点位置
max_heapify(heap, heapsize, root)
# 堆排序
def sort_heap(heap, heapsize, sortsize):
'''
heapsize:heap的长度
sortsize：未排序的数据个数
'''
build_heap(heap, heapsize) # 排序前先建立一个最大堆
heap[0], heap[sortsize] = heap[sortsize], heap[0]
heapsize -= 1 # 最大值移到最后一位之后，将其从树中删除
sortsize -= 1 # 未排序个数减1
if sortsize != 0:
sort_heap(heap, heapsize, sortsize)
计数排序
import random
def countingsort(alist, k):
n = len(alist)
b = [0 for i in range(n)]
c = [0 for i in range(k 1)]
for i in alist:
c[i] = 1
for i in range(1, len(c)):
c[i] = c[i - 1] c[i]
for i in alist:
b[c[i] - 1] = i
c[i] -= 1
return b
if __name__ == '__main__':
a = [random.randint(0, 100) for i in range(100)]
print(countingsort(a, 100))
桶排序
import random
class bucketsort(object):
def _max(self, oldlist): # 返回最大值
_max = oldlist[0]
for i in oldlist:
if i > _max:
_max = i
return _max
def _min(self, oldlist): # 返回最小值
_min = oldlist[0]
for i in oldlist:
if i < _min:
_min = i
return _min
def sort(self, oldlist):
_max = self._max(oldlist)
_min = self._min(oldlist)
s = [0 for i in range(_min, _max 1)] # 初始值都是0的桶
for i in oldlist:
s[i - _min] = 1
current = _min
n = 0
for i in s:
while i > 0:
oldlist[n] = current
i -= 1
n = 1
current = 1
def __call__(self, oldlist):
self.sort(oldlist)
return oldlist
if __name__ == '__main__':
a = [random.randint(0, 100) for i in range(10)]
bucketsort()(a)
print(a)
二叉树遍历
前序遍历
# 前序遍历
def preorder(root):
if not root:
return []
return [root.val] preorder(root.left) preorder(root.right)
# 前序遍历的非递归实现 中左右
def preordertraversal(root):
stack = [] # 右节点压入栈中，左节点递归
sol = []
curr = root
while stack or curr:
if curr:
sol.append(curr.val)
stack.append(curr.right)
curr = curr.left
else:
curr = stack.pop()
return sol
中序遍历
# 中序遍历的递归版本
def inordertraversal(root):
if not root:
return []
return inordertraversal(root.left) [root.val] inordertraversal(root.right)
# 中序遍历的非递归版本
def inordertraversal(self, root):
stack = [] # 把中间节点压入栈中
sol = []
curr = root
while stack or curr:
if curr:
stack.append(curr)
curr = curr.left
else:
curr = stack.pop()
sol.append(curr.val)
curr = curr.right
return sol
后序遍历
# 后序遍历的递归实现
def postordertraversal(self, root): ##后序遍历
if not root:
return []
return self.inordertraversal(root.left) self.inordertraversal(root.right) [root.val]
# 后序遍历的非递归实现 左右中 [::-1] 中右左
def postordertraversal(self, root): ## 后序遍历
stack = [] # 把左节点压入栈中，指针沿着右节点走
sol = []
curr = root
while stack or curr:
if curr:
sol.append(curr.val)
stack.append(curr.left)
curr = curr.right
else:
curr = stack.pop()
return sol[::-1]
广度优先遍历
# 广度优先递归实现
class solution:
def levelorder(self, root):
def helper(node, level):
if not node:
return
else:
sol[level-1].append(node.val)
if len(sol) == level: # 遍历到新层时，只有最左边的结点使得等式成立
sol.append([])
helper(node.left, level 1)
helper(node.right, level 1)
sol = [[]]
helper(root, 1)
return sol[:-1]
# 广度优先遍历的非递归实现
class solution:
def levelorder(self, root):
if not root:
return []
sol = []
curr = root # 树的遍历一般都会使用到栈这个结构
queue = [curr]
while queue:
curr = queue.pop(0)
sol.append(curr.val)
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
return sol
海量数据top k算法
寻找最大的k个数
方法一：先对数据进行排序，然后取前k个
时间复杂度：o(k n*logn)
方法二：维持一个最小堆，如果数值小于堆顶，就直接pass，如果大于堆顶，就直接替换堆顶，然后重新整理最小堆，整理一次的时间复杂度是logk
时间复杂度：o( k (n-k)*logk )
方法三：类似quick select
# 海量数据top k
def partition(seq):
qviot, seq = seq[0], seq[1:] # 选取并移除主元
right = [x for x in seq if x <= qviot] # 值较小的
left = [x for x in seq if x > qviot]
return right, qviot, left
def select(seq, k):
right, qviot, left = partition(seq)
m = len(right)
if m == k:
return right
if m < k:
right.append(qviot)
return right select(left, k-m-1)
return select(right, k)
if __name__ == "__main__":
sel = [8,3,4,5,1,5,23,5,1,3,53,645,314,632,65,76,2,46,575,1,5]
print(select(sel, 5))
哈希表
什么是哈希函数？
哈希表（hash table，也叫散列表），是根据关键码值(key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
常用的哈希函数有哪些？
- 直接定址法
取关键字或关键字的某个线性函数值为散列地址。
即 h(key) = key 或 h(key) = a*key b，其中a和b为常数。 - 除留余数法
取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
即 h(key) = key % p, p < m。 - 数字分析法
当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。 - 平方取中法
先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
随机分布的关键字，得到的散列地址也是随机分布的。 - 折叠法（叠加法）
将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。 - 随机数法
选择一个随机函数，把关键字的随机函数值作为它的哈希值。
通常当关键字的长度不等时用这种方法。
解决冲突的方法：
- 开放地址法：除了哈希函数得出地址可用，当出现冲突的时候其他地址一样可以使用
- 再哈希法：按顺序规定多个哈希函数，每次查询时按顺序调用哈希函数
- 链地址法：所有关键字哈希值都存储在同一线性链表中
- 公共溢出区：一旦发生冲突全进入溢出表
- 装填因子： a=（表中填入记录数）／（哈希表长度）
a越小，冲突越小，0.75 比较合适
二叉树：
二叉树：
二叉树是每个节点最多有两个子树的树结构
二叉树有以下几个性质：todo(上标和下标)
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n 1)。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2 1。
满二叉树，完全二叉树和二叉查找树
满二叉树
定义：高度为h，并且由2{h} –1个结点的二叉树，被称为满二叉树。
完全二叉树
定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。
二叉查找树
定义：二叉查找树(binary search tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。
b树：
b 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有m-1个子节点。
- 根节点至少有两个子节点
- 每个节点有m-1个key，并且以升序排列
- 位于m-1和m key的子节点的值位于m-1 和m key对应的value之间
- 其它节点至少有m/2个子节点
下图是一个m=4 阶的b树:
b 树：
b 树是对b树的一种变形树，它与b树的差异在于：
- 有k个子结点的结点必然有k个关键码；
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
b 树的优点在于： - b 树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而b树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有b 树好。
- 由于b 树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
剖析2：为什么b 树比b树更适合做系统的数据库索引和文件索引
1）b 树的磁盘读写代价更低
因为b 树内部结点没有指向关键字具体信息的指针，内部结点相对b树小
2）b 树的查询更加稳定
因为非终端结点并不是指向文件内容的结点，仅仅是作为叶子结点的关键字索引，因此所有的关键字查询都会走一条从根节点到叶子结点的路径。即s所有关键字查询的长度是一样的，查询效率稳定。