（针对相同元素值的快速排序）对于下列随机化快速排序分析中，我们假设输入元素的值是互异的，在本题中，我们将看看如果这一假设不成立会出现什么情况。
a.如果所有输入元素的值都相同，那么随机化快速排序的运行时间是多少？
b.PARTITION过程返回一个数组下标q，使得A[p...q-1]中的每个元素都小于或等于A[q]，而A[q+1...r]中的每个元素都大于A[q]。修改PARTITION代码来构造一个新的PARTITION'(A,p,r)，它排序A[p...r]的元素，返回值是两个数组下标q和t，其中
，且有
- A[q...t]中的所有元素都相等
- A[p...q-1]中的每个元素都小于A[q]
- A[t+1...r]中的每个元素都大于A[q]
c.将RANDOMIZED-QUICKSORT过程改为调用PARTITION'，并重新命名为RANDOMIZED-QUICKSORT'。修改QUICKSORT的代码构造一个新的QUICKSORT'（A,p,r），它调用RANDOMIZED-PARTITION'，并且只有分区内的元素互不相同的时候才做递归调用。
d.在QUICKSORT'中，应该如何改变期望时间分析方法，从而避免所有元素都是互异的这一假设？
RAMDOMIZED-PARTITION (A,p,r) i = RAMDOM (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 ifA[j]≤ x i =i+1 exchange A[i] with A[j] exchange A[i+1] with A[r] return i+1 RANDOMIZED-QUICKSORT(A,p,r) if p<r q=RANDOMIZED-PARTITION(A,p,r) RANDOMIZED-QUICKSORT(A,p,q-1) RANDOMIZED-QUICKSORT(A,q+1,r)
