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

答题要点

快速排序是一种分治算法，其基本思想是先选择一个基准元素，将数组分为两部分，使得左部分的元素都小于等于基准元素，右部分的元素都大于基准元素。然后分别对左右两部分递归地进行快速排序，最终得到一个有序的数组。快速排序的平均时间复杂度为 O(n log n)，这是因为每次划分操作能将问题规模大致减半，递归深度为 log n，每次划分需要遍历数组一次，时间复杂度为 O(n)。但在最坏情况下，例如数组已经有序，每次选择的基准元素都是最小或最大的元素，此时时间复杂度会退化为 O(n^2)。不过，通过随机选择基准元素等优化方法，可以有效降低最坏情况出现的概率，使得快速排序在大多数情况下都能保持较好的性能。