搜索--常见面试问题

1. 快速排序实现

要点：分治思想 + 原地分区

def quick_sort(arr, low=0, high=None):if high is None:high = len(arr) - 1if low < high:pi = partition(arr, low, high)  # 获取分区点quick_sort(arr, low, pi-1)      # 递归排序左子数组quick_sort(arr, pi+1, high)     # 递归排序右子数组def partition(arr, low, high):pivot = arr[high]  # 选择最右元素作为基准i = low            # 小于pivot的边界指针for j in range(low, high):if arr[j] < pivot:arr[i], arr[j] = arr[j], arr[i]  # 交换元素i += 1arr[i], arr[high] = arr[high], arr[i]  # 将pivot放到正确位置return i

复杂度：平均O(n log n)，最坏O(n²)（可通过随机化pivot避免）

关键优化策略

优化1：三数取中法（避免最坏情况）

<