给出快速排序的最坏时间复杂度和最好时间复杂度的递推公式，分析算法时间复杂度，并给出推导过程。

快速排序的最坏时间复杂度为O(n^2)，最好时间复杂度为O(nlogn)。

快速排序的时间复杂度主要取决于分区点的选择，最坏情况下，每次选择的分区点都是当前序列中的最大（或最小）值，导致分区不平衡，时间复杂度退化为O(n^2)。最好情况下，每次选择的分区点都是当前序列的中位数，导致分区比较平衡，时间复杂度为O(nlogn)。

具体推导过程如下：

首先，快速排序的基本思想是选取一个“基准值”（pivot），将序列中小于基准值的元素放在基准值的左侧，大于基准值的元素放在基准值的右侧，然后对左右两个子序列分别进行递归排序。

在每一次递归过程中，选择基准值的方式会对时间复杂度产生影响。一般情况下，可以采用以下三种方式：

1. 选择第一个元素作为基准值；
2. 选择最后一个元素作为基准值；
3. 选择随机元素作为基准值。

为了方便，我们假设每次选择第一个元素作为基准值。然后对于一个长度为n的序列，我们可以将其分为左右两个子序列S1和S2，其中S1中的元素都小于等于基准值，S2中的元素都大于基准值。具体过程如下：

1. 初始化i=1，j=n，将第一个元素作为基准值pivot；
2. 从右往左扫描序列，找到第一个小于基准值的元素S[j]，将其与S[i]交换；
3. 从左往右扫描序列，找到第一个大于基准值的元素S[i]，将其与S[j]交换；
4. 重复执行步骤2和3，直到i=j为止；
5. 递归对S1和S2进行排序。

在最好情况下，每次选择的基准值都正好将序列分为长度相等的两个子序列，即S1和S2的长度均为n/2。此时，快速排序的时间复杂度可以写成如下递推公式：

T(n) = 2T(n/2) + O(n)

其中，第一项2T(n/2)表示对S1和S2分别进行递归排序的时间复杂度，第二项O(n)表示分区过程的时间复杂度。根据主定理，可以得到T(n) = O(nlogn)。

在最坏情况下，每次选择的基准值都是当前序列中的最大或最小值，导致S1或S2的长度为0，另一侧的长度为n-1。此时，快速排序的时间复杂度可以写成如下递推公式：

T(n) = T(n-1) + O(n)

其中，第一项T(n-1)表示对长度为n-1的子序列进行递归排序的时间复杂度，第二项O(n)表示分区过程的时间复杂度。根据递推公式，可以得到T(n) = O(n^2)。

因此，快速排序的时间复杂度在最好情况下为O(nlogn)，最坏情况下为O(n^2)。