算法导论 — 思考题7-2 针对相同元素值的快速排序

（针对相同元素值的快速排序）在7.4.2节对随机化快速排序的分析中，我们假设输入元素的值是互异的。在本题中，我们将看看如果这一假设不成立会出现什么情况。
　　a. 如果所有输入元素的值都相同，那么随机化快速排序的运行时间会是多少？
　　b. ${\rm PARTITION}$PARTITION过程返回一个数组下标$q$q，使得$A[p..q-1]$A[p..q−1]中的每个元素都小于或等于$A[q]$A[q]，而$A[q+1..r]$A[q+1..r]中的每个元素都大于$A[q]$A[q]。修改${\rm PARTITION}$PARTITION代码来构造一个新的${\rm PARTITION’}(A, p, r)$PARTITION’(A,p,r)，它排列$A[p..r]$A[p..r]的元素，返回值是两个数组下标$q$q和$t$t，其中$p ≤ q ≤ t ≤ r$p≤q≤t≤r，且有
　　• $A[q..t]$A[q..t]中的所有元素都相等
　　• $A[p..q-1]$A[p..q−1]中的每个元素都小于$A[q]$A[q]
　　• $A[t+1..r]$A[t+1..r]中的每个元素都大于$A[q]$A[q]
　　与${\rm PARTITION}$PARTITION类似，新构造的${\rm PARTITION’}$PARTITION’的时间复杂度是$Θ(r-p)$Θ(r−p)。
　　c. 将${\rm RANDOMIZED-PARTITION}$RANDOMIZED−PARTITION过程改为调用${\rm PARTITION’}$PARTITION’，并重新命名为${\rm RANDOMIZED-PARTITION’}$RANDOMIZED−PARTITION’。修改${\rm QUICKSORT}$QUICKSORT的代码构造一个新的${\rm QUICKSORT’}(A, p, r)$QUICKSORT’(A,p,r)，它调用${\rm RANDOMIZED-PARTITION’}$RANDOMIZED−PARTITION’，并且只有分区内的元素互不相同的时候才做递归调用。
　　d. 在${\rm QUICKSORT’}$QUICKSORT’中，应该如何改变7.4.2节中的分析方法，从而避免所有元素都是互异的这一假设？
　　
　　解
　　a.　　
　　如果数组的所有元素都相同，那么随机化快速排序每次递归产生一个最不均衡的划分，因此运行时间为$Θ(n^2)$Θ(n2)。
　　
　　b.
　　
　　c.
　　
　　d.
　　笔者还没想明白，希望有高手来解答。
　　
　　代码链接：https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter07/Problem_7-2/SameElemQuickSort