7.1-1

（a） 首先$x=A[12]=11,i=0,j=1$，此时我们比较$A[1]和x可知A[1]gt x$，故令$j=j+1=2$；
（b） 然后比较$A[2]和x可知A[2]gt x$，故继续令$j=j+1=3$；
（c） 比较$A[3]和x可知A[3]lt x$，故令$i=i+1=1$，并交换$A[i]$即$A[1]$和$A[3]$得到新数组$A_1=9, 19, 13, 5, 12, 8, 7, 4, 21, 2, 6, 11}$；
（d） 重复上述过程，最后得到序列$A_2={9, 5, 8, 7, 4, 2, 6, 12, 21, 13, 19, 11}$，此时$i=7,j=11$，交换$A[i+1]$即$A[8]和A[12]$，最终得到$A_3={9, 5, 8, 7, 4, 2, 6, 11, 12, 21, 13, 19}$，并返回$i+1=8$。

7.1-2

返回的$q=r$；
在算法中加入一个计数器即可：

PARTITION_1(A,p,r)
1  x = A[r]
2  i = p - 1
3  count = 0
4  for j = p to r - 1
5    if A[j]<= x
6      if A[i] == x
7        count = count + 1
8      i = i + 1
9      exchange A[i] with A[j]
10 if count == r - p + 1
11   return lfloor (p + r)/2 rfloor
12 exchange A[i + 1] with A[r]
13 return i + 1

7.1-3

在规模为$n$的子数组运行PARTITION需要进行$n-1$次比较，每次比较时间复杂度为$Theta(1)$，所以整个算法的复杂度为$Theta(n)$。

7.1-4

将PARTITION算法的第4行换为$A[j] ge x$即可。

最后

以上就是清新鸵鸟为你收集整理的算法导论第三版习题7.17.1-17.1-27.1-37.1-4的全部内容，希望文章能够帮你解决算法导论第三版习题7.17.1-17.1-27.1-37.1-4所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。