4-2 Python面试常考算法

一、算法常考点

排序+查找，重中之重

1.常考排序算法：冒泡排序、快速排序、归并排序、堆排序
2.线性查找、二分查找等
3.能独立实现代码（手写），能够分析时间空间复杂度

二、常用排序算法时空复杂度

三、排序算法中的稳定性

什么是排序算法的稳定性？
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)

说明：一般面试时，写出非递归方式实现二分查找即可，因为效率会更高一些。