请简述快速排序的基本思想和时间复杂度。

答题要点

快速排序是一种分治算法，其基本思想是通过选择一个基准元素，将数组分为两部分，使得左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于基准元素，然后分别对左右两部分递归地进行排序。具体步骤如下：首先选择一个基准元素，通常选择数组的第一个元素或随机选择一个元素；然后将数组中小于等于基准元素的元素移到左边，大于基准元素的元素移到右边；最后递归地对左右两部分进行排序。快速排序的平均时间复杂度为 O(n log n)，这是因为每次划分操作将数组分为两部分，递归深度为 log n，每次划分操作的时间复杂度为 O(n)。然而，在最坏情况下，即数组已经有序时，快速排序的时间复杂度会退化为 O(n^2)。为了避免最坏情况的发生，可以采用随机选择基准元素的方法。