算法导论第三版第七章课后答案

7.1-1 参照图7-1的方法，说明PARTITION在数组A={13,9,9,5,12,8,7,4,21,2,6,11}上的操作过程。

A={13,19,9,5,12,8,7,4,21,2,6,11}

  ={13,19,9,5,12,8,7,4,21,2,6,11}

  ={13,19,9,5,12,8,7,4,21,2,6,11}

  ={9,19,13,5,12,8,7,4,21,2,6,11}

  ={9,5,13,19,12,8,7,4,21,2,6,11}

  ={9,5,13,19,12,8,7,4,21,2,6,11}

  ={9,5,8,19,12,13,7,4,21,2,6,11}

  ={9,5,8,7,12,13,19,4,21,2,6,11}

  ={9,5,8,7,4,13,19,12,21,2,6,11}

  ={9,5,8,7,4,13,19,12,21,2,6,11}

  ={9,5,8,7,4,2,19,12,21,13,6,11}

  ={9,5,8,7,4,2,6,12,21,13,19,11}

  ={9,5,8,7,4,2,6,11,21,13,19,12}

7.1-2 当数组A[p..r]中的元素都相同时，PARTITION返回的q值是什么？修改PARTITION，使得当数组A[p..r]中所有元素的值都相同时，q=(p+r)/2.

当元素相同时,q=i+1=r-1+1=r.

修改后的函数q=(p+r)/2.

除了函数内数个O(1)，还有一个循环,其循环次数 p-(r-1)+1=p-r次，O(p-r)=O(n)

7.1-4  如何修改QUICKSORT，使得它能够以非递增序进行排序？

仅仅需要把  x >=A[i] 改为 x 0) n>0 当c>2c2>0时，有n>0,对于足够大的n都成立。

 所以存在常数c1>c/2,c2=n0时，对于足够大的n都成立，T(n)=Θ(n^2)成立 

 7.2-2当数组A的所有元素都具有相同值时，QUICKSORT的时间复杂度是什么？  

 当数组A所有元素相同时，QUICKSORT中的划分时极为不平衡的,n-1:0的划分,T(n)=T(n-1)+Θ(n)解这个递归式T(n)=Θ(n^2) 

 7.2-3 证明：当数组A包含的元素不同，并且是按降序排列的时候，QUICKSORT的时间复杂度为Θ(n^2)

 按照降序排序时，在QUICKSORT中的划分时极为不平衡的,n-1:0的划分，所以其时间复杂度为T(n)=T(n-1)+Θ(n)解这个递归式  T(n)=T(n)=Θ(n^2)

 7.2-4 银行一半会按照交易时间来记录某一账户的交易情况。但是，很多人却喜欢收到银行对账单是按照支票号码的顺序来排列的。这是因为，人们通常  都是按照支票号码的顺序来开出支票的，而商人也通常都是根据支票编号的顺序兑付支票。这一问题时按照交易时间排序的序列转换成按支票号排序的  序列，它是指上是一个对几乎有序的输入序列进行排序的问题。请证明：在这个问题上，INSERTION-SORT的性能往往要优于QUICKSORT？

插入排序在基本有序的情况下，基本无需移动任何元素来插入，所以只有外层循环了n次，所以时间复杂度为O(n)

 快速排序在基本有序的情况下，在划分数组时，划分得非常不平衡，那么其时间复杂度是O(nlgn),而达到完全有序时，时间 复杂度达到O(n^2)，

所以总之插入排序要优于快速排序。 

7.2-5 假设快速排序的每一层所做的划分的比例都是1-a:a，其中00         

                              3）当a