一 、算法常考点
排序+查找 ，重中之重
1.常考排序算法：冒泡排序 、快速排序、归并排序 、堆排序
2.线性查找 、二分查找等
3.能独立实现代码（手写） ，能够分析时间空间复杂度
二、常用排序算法时空复杂度
| 排序算法 | 最差时间分析 | 平均时间复杂度 | 稳定性 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) |
O(n^2) |
稳定 | O(1) |
| 选择排序 | O(n^2) |
O(n^2) |
不稳定 | `O(1) |
| 插入排序 | O(n^2) |
O(n^2) |
稳定 | `O(1) |
| 快速排序 | O(n^2) |
O(n*log2n) |
不稳定 | O(log2n)~O(n) |
| 堆排序 | O(n*log2n) |
O(n*log2n) |
不稳定 | O(1) |
三 、排序算法中的稳定性
什么是排序算法的稳定性？
1.相同大小的元素在排序之后依然保持相对位置不变，就是稳定的
2.r[i] = r[j] 且 r[i] 在r[j]之前 ，排序之后 r[i] 依然在 r[j] 之前
3.稳定性对于排序一个复杂结构 ，并且需要保持原有排序才有意义
四 、请写出快速排序
快排经常问：分治法（divide and conquer）快排分三步走
1.Partition：选择基准分割数组为两个子数组，小于基准和大于基准的
2.对两个子数组分别快排
3.合并结果
代码示例：
def quick_sort(arr):
# 递归出口 ，空数组或者只有一个元素的数组都是有序的
if len(array) < 2:
return array
else:
pivot_index = 0 # 第一个元素作为 pivot（主元）
pivot = array[pivot_index]
less_part = [
i for i in array[pivot_index+1:] if i <= pivot
]
great_part = [
i for i in array[pivot_index+1:] if i > pivot
]
return quick_sort(less_part) + [pivot] + quick_sort(great_part)
def test_quick_sort():
import random
ll = list(range(10))
random.shuffle(ll)
print(ll)
assert quick_sort(ll) == sorted(ll)
用pytest运行结果：
五、合并两个有序数组
合并两个有序数组 ，要求 a[n], b[m], O(n+m)
def merge_sorted_list(sorted_a, sorted_b):
""" 合并两个有序序列，返回一个新的有序序列 """
length_a, length_b = len(sorted_a), len(sorted_b)
a = b = 0
new_sorted_seq = list()
while a < length_a and b < length_b:
if sorted_a[a] < sorted_b[b]:
new_sorted_seq.append(sorted_a[a])
a += 1
else:
new_sorted_seql.append(sorted_b[b])
b += 1
# 最后别忘记把多余的都放到有序数组里
while a < length_a:
new_sorted_seq.append(sorted_a[a])
a += 1
while b < length_b:
new_sorted_seq.append(sorted_b[b])
b += 1
# 上面两个 while，也可以写成下面的 if else
# if a < length_a:
# new_sorted_seq.extend(sorted_a[a:])
# else:
# new_sorted_seq.extend(sorted_b[b:])
return new_sorted_seq
def test_merge_sorted_list():
a = [1, 3, 5]
b = [0, 2 ,4,8]
c = merge_sorted_list(a, b)
print(c)
图示：
六、请实现归并排序
前边我们实现了合并两个有序数组 ，在此基础上实现归并排序
分治法三步走 。注意递归出口
# 上边实现了合并两个有序数组 ，实现归并排序就非常方便了
def merge_sort(seq):
if len(seq) <= 1: # 只有一个元素是递归出口
return seq
else:
mid = int(len(seq)/2)
left_half = merge_sort(seq[:mid])
right_half = merge_sort(seq[mid:])
# 合并两个有序的数组
new_seq = merge_sorted_list(left_half, right_half)
return new_seq
def test_merge_sort():
import random
ll = list(range(10))
random.shuffle(ll)
print(ll)
assert merge_sort(ll) == sorted(ll)
七 、请实现堆排序
短时间内实现堆还是有困难的，但可以借助 heapq模块快速实现
def heapsort_use_heapq(iterable):
from heapq import heappush, heappop
items = []
for value in iterable:
heappush(items, value)
return [heappop(items) for i in range(len(items))]
注意：请先查看下 heapq 模块文档
八 、请写出二分查找
def binary_search(sorted_array, val):
if not sorted_array:
return -1
beg = 0
end = len(sorted_array) - 1
while beg <= end:
mid = int(len(beg + end)/2) # beg + (end-beg)/2 ，为了屏蔽 python 2/3 差异这里用了强制转换
if sorted_array[mid] == val:
return mid
elif sorted_array[mid] > val:
end = mid - 1
elif:
beg = mid + 1
return -1
说明：二分查找经常让手写 ，注意边界（其实 python有个bisect模块）
如下图示：
递归方式实现二分，注意递归出口
def binary_search_recursive(sorted_array, beg, end, val):
if beg >= end:
return -1
mid = int((beg + end) / 2) # beg + (end - beg) / 2
if sorted_array[mid] == val:
return mid
elif sorted_array[mid] > val:
# 注意依然假设 beg, end 区间是左闭右开的
return binary_search_recursive(sorted_array, beg, mid, val)
else:
return binary_search_recursive(sorted_array, mid + 1, end, val)
说明：一般面试时 ，写出非递归方式实现二分查找即可 ，因为效率会更高一些 。
本文版权归趣快排SEO www.SeogurUblog.com 所有,如有转发请注明来出,竞价开户托管,seo优化请联系QQ▶61910465