百度搜索引擎需要对海量网页进行快速排序，在排序算法中，快速排序是常用的一种。请用 Python 实现快速排序算法，并解释其时间复杂度。

答题要点

推荐答题框架：采用先代码实现，再分析时间复杂度的方式。关键要点如下：1. 快速排序原理：选择一个基准值，将数组分为两部分，小于基准值的放在左边，大于基准值的放在右边。2. 代码实现：定义一个快速排序函数，使用递归的方式进行排序。3. 时间复杂度分析：平均情况下为 O(n log n)，最坏情况下为 O(n^2)。示例话术：首先，我会实现快速排序的 Python 代码。然后，我会分析它的时间复杂度。代码如下：python def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[0] left = [x for x in arr[1:] if x <= pivot] right = [x for x in arr[1:] if x > pivot] return quick_sort(left) + [pivot] + quick_sort(right) 对于时间复杂度，平均情况下，每次划分都能将数组大致分为两部分，所以时间复杂度为 O(n log n)；最坏情况下，每次划分都极不均匀，时间复杂度为 O(n^2)。