非序 for i=high; i>low; i--) ∥反向起泡 if( Vectori-1>Vector)i ∥发生逆序 Swap( Vector[i-1, Vector); ∥交换 ∥记忆左边最后发生交换的位置j ∥比较范围下界缩小到 9-5如果待排序的排序码序列已经按非递减次序有序排列,试证明函数 Quick Sor)的计算 时间将下降到Om2)。 【证明】 若待排序的n个对象的序列已经按排序码非递减次序有序排列,且设排序的时间代价为 T(n)。当以第一个对象作为基准对象时,应用一次划分算法 Partition,通过n-1次排序码比 较,把只能把整个序列划分为:基准对象的左子序列为空序列,右子序列为有n1个对象的 非递减有序序列。对于这样的递归 Quick Sort()算法,其时间代价为 T(n)=(n-1)+T(n-1) =(n-1)+{(n-2)+T(n-2)} (n-1)+(n-2)+{(n-3)+T(n-3)} =(n-1)+(n-2)+(n-3)+…+{2+T(1)} (n-1)+(n-2)+(n-3) 2+1 n(n-1)/2=O(n2) 9-6在实现快速排序的非递归算法时,可根据基准对象,将待排序排序码序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序,试证明在此做法下,快速排序所需要的栈的 深度为O(logn) 【解答】 由快速排序的算法可知,所需递归工作栈的深度取决于所需划分的最大次数。如果在排 序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两 个子序列的长度相等,则所需栈的深度为 S(n)=1+S(n/2)= =1+{1+S(n/4)}=2+S(n/4) =2+{1+S(n/8)}=3+S(n/8) logan+ S(1)=log2n (假设1个对象的序列所用递归栈的深度为0) 如果每次递归左、右子序列的长度不等,并且先将较长的子序列的左、右端点保存在递 归栈中,再对较短的子序列进行排序,可用表示最坏情况的大O表示法表示。此时其递归 栈的深度不一定正好是logn,其最坏情况为 O(log2n)。 9-7在实现快速排序算法时,可先检查位于两端及中点的排序码,取三者之中的数值不是最 大也不是最小的排序码作为基准对象。试编写基于这种思想的快速排序算法,并证明对于已 排序的排序码序列,该算法的计算时间为 o(nlog2n) 【解答】参看教科书 9-8在使用非递归方法实现快速排序时,通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈?为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中,通过一趟划分,可以把一个待排序区间分第 9 章 排序 10 for ( i = high; i > low; i-- ) //反向起泡 if ( Vector[i-1] > Vector[i] ) { //发生逆序 Swap ( Vector[i-1], Vector[i] ); //交换 j = i; //记忆左边最后发生交换的位置 j } low = j; //比较范围下界缩小到 j } } 9-5 如果待排序的排序码序列已经按非递减次序有序排列，试证明函数 QuickSort( )的计算 时间将下降到 O(n2 )。 【证明】 若待排序的 n 个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为 T(n)。当以第一个对象作为基准对象时，应用一次划分算法 Partition，通过 n-1 次排序码比 较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有 n-1 个对象的 非递减有序序列。对于这样的递归 QuickSort( )算法，其时间代价为 T(n) = (n-1) + T(n-1) = (n-1) + {( n-2) + T(n-2) } = (n-1) + (n-2) + {(n-3) + T(n-3) } = …… = (n-1) + (n-2) + (n-3) + … + { 2 + T(1) } = (n-1) + (n-2) + (n-3) + … + 2 + 1 = n(n-1)/2 = O(n2 ) 9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的 深度为 O(log2n)。 【解答】 由快速排序的算法可知,所需递归工作栈的深度取决于所需划分的最大次数。如果在排 序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两 个子序列的长度相等，则所需栈的深度为 S(n) = 1 + S(n/2) = = 1 + { 1 + S(n/4) } = 2 + S(n/4) = 2 + { 1 + S(n/8) } = 3 + S(n/8) = …… = log2n + S(1) = log2n (假设 1 个对象的序列所用递归栈的深度为 0) 如果每次递归左、右子序列的长度不等，并且先将较长的子序列的左、右端点保存在递 归栈中，再对较短的子序列进行排序，可用表示最坏情况的大 O 表示法表示。此时其递归 栈的深度不一定正好是 log2n，其最坏情况为 O(log2n)。 9-7 在实现快速排序算法时，可先检查位于两端及中点的排序码，取三者之中的数值不是最 大也不是最小的排序码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已 排序的排序码序列，该算法的计算时间为 O(nlog2n)。 【解答】参看教科书 9-8 在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈? 为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分