1.写出随机化快排序算法，并分析算法在最好情况下的时间复杂度。

随机化快速排序是一种基于分治思想的经典排序算法，其基本思路是先选取一个基准元素，然后将待排序序列划分成左右两个部分，左部分所有元素均小于等于基准元素，右部分所有元素均大于等于基准元素，然后分别对左右两个部分递归地进行排序。

具体实现时，随机化快速排序算法会先从待排序序列中随机选取一个元素作为基准元素，然后将序列中所有小于等于该元素的元素都放到该元素左边，所有大于等于该元素的元素都放到该元素右边，最后再递归对左右两个子序列进行排序。

下面是随机化快速排序算法的伪代码描述：

QUICKSORT(A, p, r)
if p < r
    q = RANDOMIZED-PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)

RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION(A, p, r)

PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

在最好情况下，每次划分都恰好将待排序序列均分为大小相等的两部分，即每次划分都能得到一个与当前序列规模相等的子序列。此时，随机化快速排序的时间复杂度为O(n log n)，与归并排序一样具有较好的时间效率。