测开面试 | Python常问算法

1、排序

• 从小到大排序：sorted(list)
• 从大到小排序：sorted(list, reverse=True)
• sort() 方法，改变原有数组的顺序
• sort(reverse=True)

复制代码#!/bin/Python alist = [1, 4, 2, 3, 7, 6] print(sorted(alist)) print(sorted(alist, reverse=True)) alist.sort() print(alist) alist.sort(reverse=True) print(alist)

1
2
3
4
5
6
7
8
#!/bin/Python
alist = [1, 4, 2, 3, 7, 6]
print(sorted(alist))
print(sorted(alist, reverse=True))
alist.sort()
print(alist)
alist.sort(reverse=True)
print(alist)

2、冒泡

• 1.比较相邻的元素，如果第一个比第二个大，就交换
• 2.一轮遍历，每两个相邻的元素，重复第 1 步，最大的放队尾
• 3.不包括已经排队尾的，重复第 2 步

复制代码#!/bin/Python # -*- coding: UTF-8 -*- #冒泡排序 def bubble_sort(lists): #获取数组长度 count = len(lists) - 1 #N个元素遍历N次 for index in range(count, 0, -1): #第i个和i+1个依次对比 for sub_index in range(index): #大的元素冒上去 if lists[sub_index] > lists[sub_index + 1]: lists[sub_index], lists[sub_index + 1] = lists[sub_index + 1], lists[sub_index] return lists alist = [1, 4, 2, 3, 7, 6] print(bubble_sort(alist))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/bin/Python
# -*- coding: UTF-8 -*-
#冒泡排序
def bubble_sort(lists):
#获取数组长度
count = len(lists) - 1
#N个元素遍历N次
for index in range(count, 0, -1):
#第i个和i+1个依次对比
for sub_index in range(index):
#大的元素冒上去
if lists[sub_index] > lists[sub_index + 1]:
lists[sub_index], lists[sub_index + 1] = lists[sub_index + 1], lists[sub_index]
return lists
alist = [1, 4, 2, 3, 7, 6]
print(bubble_sort(alist))

3、快排

• 1.从列表中挑出一个元素，作为基准值 key
• 2.所有小于 key 的元素放左边，所有大于 key 的元素放右边
• 3.分别递归左侧列表，右侧列表

复制代码#!/bin/Python # -*- coding: UTF-8 -*- #快速排序 def quick_sort(lists, left, right): #递归过程中，发现left和right一致时，停止递归，直接返回列表 if left >= right: return lists #定义游标 low = left high = right #取参考标志，最左边的元素 key = lists[low] while low < high: #从最右侧向左，依次和标志元素对比，如果右侧的元素大于等于标志元素 while low < high and lists[high] >= key: #右侧减1 high -= 1 #如果右侧的元素小于标志元素，则low赋high值 lists[low] = lists[high] #从最左侧向右，依次和标志元素对比，如果左侧的元素小于等于标志元素 while low < high and lists[low] <= key: #左侧加1 low += 1 #如果左侧的元素大于标志元素，则high赋low值 lists[high] = lists[low] #最后给high位置赋值 lists[high] = key #处理左侧元素 quick_sort(lists, left, low - 1) #处理右侧元素 quick_sort(lists, low + 1, right) return lists alist = [0, 10, 88, 19, 9, 1, 7] print(quick_sort(alist, 0, 6))

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
#!/bin/Python
# -*- coding: UTF-8 -*-
#快速排序
def quick_sort(lists, left, right):
#递归过程中，发现left和right一致时，停止递归，直接返回列表
if left >= right:
return lists
#定义游标
low = left
high = right
#取参考标志，最左边的元素
key = lists[low]
while low < high:
#从最右侧向左，依次和标志元素对比，如果右侧的元素大于等于标志元素
while low < high and lists[high] >= key:
#右侧减1
high -= 1
#如果右侧的元素小于标志元素，则low赋high值
lists[low] = lists[high]
#从最左侧向右，依次和标志元素对比，如果左侧的元素小于等于标志元素
while low < high and lists[low] <= key:
#左侧加1
low += 1
#如果左侧的元素大于标志元素，则high赋low值
lists[high] = lists[low]
#最后给high位置赋值
lists[high] = key
#处理左侧元素
quick_sort(lists, left, low - 1)
#处理右侧元素
quick_sort(lists, low + 1, right)
return lists
alist = [0, 10, 88, 19, 9, 1, 7]
print(quick_sort(alist, 0, 6))

4、堆排序

• 堆排序指利用堆的数据结构设计的一种排序算法
• 堆近似于一个完全二叉树结构
• 子节点的键值小于（或者大于）它的父节点

复制代码#!/bin/Python # -*- coding: UTF-8 -*- #堆排序 def heap_sort(lst): def sift_down(start, end): """最大堆调整""" root = start print "root %d start %d end %d" % (root, start, end) while True: child = 2 * root + 1 #print "child index: %d" % child #终止条件，孩子的索引值超过数组最大长度 if child > end: break #print "lst child value: %d" % lst[child] #确定最大的孩子节点的索引值 if child + 1 <= end and lst[child] < lst[child + 1]: child += 1 #print "child+1 index: %d" % child #孩子节点最大值和根节点交换 if lst[root] < lst[child]: lst[root], lst[child] = lst[child], lst[root] #print "lstroot %d" %d lst[root], "lstchild %d" % lst[child] root = child #print "root %d" % root else: break print("---------------创建最大堆---------------") #创建最大堆 print(xrange((len(lst) - 2) // 2, -1, -1)) for start in xrange((len(lst) - 2) // 2, -1, -1): print "---->Loop start %d" % start sift_down(start, len(lst) - 1) print(lst) print("---------------排序过程---------------") #堆排序 for end in xrange(len(lst) - 1, 0, -1): #首尾交换 lst[0], lst[end] = lst[end], lst[0] #剩余重新堆排序 sift_down(0, end - 1) print(lst) return lst alist = [70, 60, 12, 40, 30, 8, 10] print(heap_sort(alist))

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
#!/bin/Python
# -*- coding: UTF-8 -*-
#堆排序
def heap_sort(lst):
def sift_down(start, end):
"""最大堆调整"""
root = start
print "root %d start %d end %d" % (root, start, end)
while True:
child = 2 * root + 1
#print "child index: %d" % child
#终止条件，孩子的索引值超过数组最大长度
if child > end:
break
#print "lst child value: %d" % lst[child]
#确定最大的孩子节点的索引值
if child + 1 <= end and lst[child] < lst[child + 1]:
child += 1
#print "child+1 index: %d" % child
#孩子节点最大值和根节点交换
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
#print "lstroot %d" %d lst[root], "lstchild %d" % lst[child]
root = child
#print "root %d" % root
else:
break
print("---------------创建最大堆---------------")
#创建最大堆
print(xrange((len(lst) - 2) // 2, -1, -1))
for start in xrange((len(lst) - 2) // 2, -1, -1):
print "---->Loop start %d" % start
sift_down(start, len(lst) - 1)
print(lst)
print("---------------排序过程---------------")
#堆排序
for end in xrange(len(lst) - 1, 0, -1):
#首尾交换
lst[0], lst[end] = lst[end], lst[0]
#剩余重新堆排序
sift_down(0, end - 1)
print(lst)
return lst
alist = [70, 60, 12, 40, 30, 8, 10]
print(heap_sort(alist))

5、二分查找

• 二分查找又称折半查找
• 必须采用顺序存储结构
• 必须按关键字大小有序排列

复制代码#!/bin/Python # -*- coding: UTF-8 -*- #二分查找 #原始数组 alist = [0, 1, 10, 88, 19, 9, 1] def binary_search(arr, start, end, hkey): if start > end: #返回-1,表示程序出现异常 return -1 #先找到数组索引的中间值 mid = start + (end - start) / 2 #如果中间值大于查找的值，则从中间值左边的数组中查找 if arr[mid] > hkey: return binary_search(arr, start, mid - 1, hkey) #如果中间值小于查找的值，则从中间值右边的数组中查找 if arr[mid] < hkey: return binary_search(arr, mid + 1, end, hkey) #返回查找的值所在的索引值 return mid #给数组排序 alist = sorted(alist) #打印出排序后的数组 print(alist) #执行程序 print binary_search(alist, 0, 6, 9)

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
#!/bin/Python
# -*- coding: UTF-8 -*-
#二分查找
#原始数组
alist = [0, 1, 10, 88, 19, 9, 1]
def binary_search(arr, start, end, hkey):
if start > end:
#返回-1,表示程序出现异常
return -1
#先找到数组索引的中间值
mid = start + (end - start) / 2
#如果中间值大于查找的值，则从中间值左边的数组中查找
if arr[mid] > hkey:
return binary_search(arr, start, mid - 1, hkey)
#如果中间值小于查找的值，则从中间值右边的数组中查找
if arr[mid] < hkey:
return binary_search(arr, mid + 1, end, hkey)
#返回查找的值所在的索引值
return mid
#给数组排序
alist = sorted(alist)
#打印出排序后的数组
print(alist)
#执行程序
print binary_search(alist, 0, 6, 9)

6、素数

• 素数又称质数
• 0，1 不是素数
• 除了 1 和它本身外，不能被其他自然数整除的数

复制代码#!/bin/Python # -*- coding: UTF-8 -*- #素数 def is_prime(n): #0，1 不是素数 if n <= 1: return False #除了 1 和它本身外，不能被其他自然数整除的数 for i in range(2, n): if n % i == 0: return False return True for i in range(0, 100): if is_prime(i): print i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/bin/Python
# -*- coding: UTF-8 -*-
#素数
def is_prime(n):
#0，1 不是素数
if n <= 1:
return False
#除了 1 和它本身外，不能被其他自然数整除的数
for i in range(2, n):
if n % i == 0:
return False
return True
for i in range(0, 100):
if is_prime(i):
print i

---

欢迎关注微信公众号"测试开发Stack"