一、算法常考点
排序+查找,重中之重
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.合并结果
代码示例:
defquick_sort(arr):# 递归出口,空数组或者只有一个元素的数组都是有序的iflen(array)<2:return arrayelse:
pivot_index=0# 第一个元素作为 pivot(主元)
pivot= array[pivot_index]
less_part=[
ifor iin array[pivot_index+1:]if i<= pivot]
great_part=[
ifor iin array[pivot_index+1:]if i> pivot]return quick_sort(less_part)+[pivot]+ quick_sort(great_part)deftest_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)
defmerge_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_aand b< length_b:if sorted_a[a]< sorted_b[b]:
new_sorted_seq.append(sorted_a[a])
a+=1else:
new_sorted_seql.append(sorted_b[b])
b+=1# 最后别忘记把多余的都放到有序数组里while a< length_a:
new_sorted_seq.append(sorted_a[a])
a+=1while 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_seqdeftest_merge_sorted_list():
a=[1,3,5]
b=[0,2,4,8]
c= merge_sorted_list(a, b)print(c)
图示:
六、请实现归并排序
前边我们实现了合并两个有序数组,在此基础上实现归并排序
分治法三步走。注意递归出口
# 上边实现了合并两个有序数组,实现归并排序就非常方便了defmerge_sort(seq):iflen(seq)<=1:# 只有一个元素是递归出口return seqelse:
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_seqdeftest_merge_sort():import random
ll=list(range(10))
random.shuffle(ll)print(ll)assert merge_sort(ll)==sorted(ll)
七、请实现堆排序
短时间内实现堆还是有困难的,但可以借助heapq
模块快速实现
defheapsort_use_heapq(iterable):from heapqimport heappush, heappop
items=[]for valuein iterable:
heappush(items, value)return[heappop(items)for iinrange(len(items))]
注意:请先查看下heapq
模块文档
八、请写出二分查找
defbinary_search(sorted_array, val):ifnot sorted_array:return-1
beg=0
end=len(sorted_array)-1while beg<= end:
mid=int(len(beg+ end)/2)# beg + (end-beg)/2,为了屏蔽 python 2/3 差异这里用了强制转换if sorted_array[mid]== val:return midelif sorted_array[mid]> val:
end= mid-1elif:
beg= mid+1return-1
说明:二分查找经常让手写,注意边界(其实python
有个bisect
模块)
如下图示:
递归方式实现二分,注意递归出口
defbinary_search_recursive(sorted_array, beg, end, val):if beg>= end:return-1
mid=int((beg+ end)/2)# beg + (end - beg) / 2if sorted_array[mid]== val:return midelif 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)
说明:一般面试时,写出非递归方式实现二分查找即可,因为效率会更高一些。