面试常见基础算法:排序/查找/树的遍历等(python版)

总结一下基本算法,以备忘,以复习。
当然,你别指望考官会直接考你这些,太基础,但是,当他知道你这些都写不出来的时候,你面试绝对没希望了。

PS: 真的有面试官会考啊,至少Baidu会考…………

8大排序

冒泡排序

稳定排序,简单易于实现,复杂度$Ο(n ^2)$

1
2
3
4
5
6
7
def bubble_sort(arr):
length = len(arr)
for i in range(length):
for j in range(i, length):
if arr[i] > arr[j]:
arr[i], arr[j] = arr[j], arr[i]
return arr

选择排序

不稳定排序,复杂度$Ο(n ^2)$

1
2
3
4
5
6
7
8
9
def select_sort(arr):
length = len(arr)
for i in range(length):
_min = i
for j in range(i+1, length):
if arr[_min] > arr[j]:
_min = j
arr[i], arr[_min] = arr[_min], arr[i]
return arr

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
def insert_sort(alist):
"""插入排序"""
n = len(alist)
for j in range(1, n):
# 控制将拿到的元素放到前面有序序列中正确位置的过程
for i in range(j, 0, -1):
# 如果比前面的元素小,则往前移动
if alist[i] < alist[i - 1]:
alist[i], alist[i - 1] = alist[i - 1], alist[i]
# 否则代表比前面的所有元素都小,不需要再移动
else:
break

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def shell_sort(alist):
"""希尔排序"""
n = len(alist)
gap = n // 2
while gap >= 1:
for j in range(gap, n):
i = j
while (i - gap) >= 0:
if alist[i] < alist[i - gap]:
alist[i], alist[i - gap] = alist[i - gap], alist[i]
i -= gap
else:
break
gap //= 2

归并排序

稳定排序,复杂度 $Ο(n log n)$ ,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def msort2(x):
if len(x) < 2:
return x
result = []
mid = int(len(x) / 2)
y = msort2(x[:mid])
z = msort2(x[mid:])
while (len(y) > 0) and (len(z) > 0):
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
result += y
result += z
return result

快速排序 QuickSort

为不稳定排序,快速排序通常明显比同为 $Ο(n log n)$ 的其他算法更快,因此常被采用,而且快排采用了分治法的思想,所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性.

1
2
3
4
5
6
7
8
9
def quicksort(arr):
if len(arr) <= 1: return arr
pivot = arr[len(arr) // 2]
left = [i for i in arr if i<pivot]
middle = [i for i in arr if i==pivot]
right = [i for i in arr if i>pivot]
return quicksort(left) + middle + quicksort(right)

堆排序 HeapSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import random
def MAX_Heapify(heap,HeapSize,root):#在堆中做结构调整使得父节点的值大于子节点
left = 2*root + 1
right = left + 1
larger = root
if left < HeapSize and heap[larger] < heap[left]:
larger = left
if right < HeapSize and heap[larger] < heap[right]:
larger = right
if larger != root:#如果做了堆调整则larger的值等于左节点或者右节点的,这个时候做对调值操作
heap[larger],heap[root] = heap[root],heap[larger]
MAX_Heapify(heap, HeapSize, larger)
def Build_MAX_Heap(heap):#构造一个堆,将堆中所有数据重新排序
HeapSize = len(heap)#将堆的长度当独拿出来方便
for i in xrange((HeapSize -2)//2,-1,-1):#从后往前出数
MAX_Heapify(heap,HeapSize,i)
def HeapSort(heap):#将根节点取出与最后一位做对调,对前面len-1个节点继续进行对调整过程。
Build_MAX_Heap(heap)
for i in range(len(heap)-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
MAX_Heapify(heap, i, 0)
return heap

基数排序

1
2
3
4
5
6
7
8
9
import random
def radixSort():
A=[random.randint(1,9999) for i in xrange(10000)]
for k in xrange(4): #4轮排序
s=[[] for i in xrange(10)]
for i in A:
s[i/(10**k)%10].append(i)
A=[a for b in s for a in b]
return A

查找:

二分查找

只适用于有序数组,复杂度$Ο(log n)$

1
2
3
4
5
6
7
8
9
10
11
def binary_search(arr, key):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key: return mid
elif arr[mid] < key:
low = mid + 1
elif arr[mid] > key:
high = mid - 1
return -1

树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
class Node(object):
"""节点类"""
def __init__(self, elem=-1, lchild=None, rchild=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
class Tree(object):
"""树类"""
def __init__(self):
self.root = Node()
self.myQueue = []
def add(self, elem):
"""为树添加节点"""
node = Node(elem)
if self.root.elem == -1: # 如果树是空的,则对根节点赋值
self.root = node
self.myQueue.append(self.root)
else:
treeNode = self.myQueue[0] # 此结点的子树还没有齐。
if treeNode.lchild == None:
treeNode.lchild = node
self.myQueue.append(treeNode.lchild)
else:
treeNode.rchild = node
self.myQueue.append(treeNode.rchild)
self.myQueue.pop(0) # 如果该结点存在右子树,将此结点丢弃。
def front_digui(self, root):
"""利用递归实现树的先序遍历"""
if root == None:
return
print root.elem,
self.front_digui(root.lchild)
self.front_digui(root.rchild)
def middle_digui(self, root):
"""利用递归实现树的中序遍历"""
if root == None:
return
self.middle_digui(root.lchild)
print root.elem,
self.middle_digui(root.rchild)
def later_digui(self, root):
"""利用递归实现树的后序遍历"""
if root == None:
return
self.later_digui(root.lchild)
self.later_digui(root.rchild)
print root.elem,
def front_stack(self, root):
"""利用堆栈实现树的先序遍历"""
if root == None:
return
myStack = []
node = root
while node or myStack:
while node: #从根节点开始,一直找它的左子树
print node.elem,
myStack.append(node)
node = node.lchild
node = myStack.pop() #while结束表示当前节点node为空,即前一个节点没有左子树了
node = node.rchild #开始查看它的右子树
def middle_stack(self, root):
"""利用堆栈实现树的中序遍历"""
if root == None:
return
myStack = []
node = root
while node or myStack:
while node: #从根节点开始,一直找它的左子树
myStack.append(node)
node = node.lchild
node = myStack.pop() #while结束表示当前节点node为空,即前一个节点没有左子树了
print node.elem,
node = node.rchild #开始查看它的右子树
def later_stack(self, root):
"""利用堆栈实现树的后序遍历"""
if root == None:
return
myStack1 = []
myStack2 = []
node = root
myStack1.append(node)
while myStack1: #这个while循环的功能是找出后序遍历的逆序,存在myStack2里面
node = myStack1.pop()
if node.lchild:
myStack1.append(node.lchild)
if node.rchild:
myStack1.append(node.rchild)
myStack2.append(node)
while myStack2: #将myStack2中的元素出栈,即为后序遍历次序
print myStack2.pop().elem,
def level_queue(self, root):
"""利用队列实现树的层次遍历"""
if root == None:
return
myQueue = []
node = root
myQueue.append(node)
while myQueue:
node = myQueue.pop(0)
print node.elem,
if node.lchild != None:
myQueue.append(node.lchild)
if node.rchild != None:
myQueue.append(node.rchild)
if __name__ == '__main__':
"""主函数"""
elems = range(10) #生成十个数据作为树节点
tree = Tree() #新建一个树对象
for elem in elems:
tree.add(elem) #逐个添加树的节点
print '队列实现层次遍历:'
tree.level_queue(tree.root)
print '\n\n递归实现先序遍历:'
tree.front_digui(tree.root)
print '\n递归实现中序遍历:'
tree.middle_digui(tree.root)
print '\n递归实现后序遍历:'
tree.later_digui(tree.root)
print '\n\n堆栈实现先序遍历:'
tree.front_stack(tree.root)
print '\n堆栈实现中序遍历:'
tree.middle_stack(tree.root)
print '\n堆栈实现后序遍历:'
tree.later_stack(tree.root)