下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴

admin2009-01-10  47

问题 下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。
   A:待排序数组
   p,r: 数组元素下标,从p到r
   q: 划分的位置
   x:枢轴元素
   i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值
   j:循环控制变量,表示数组元素下标
   QUICKSORT (A,p,r){
       if  (p <r){
           q=PARTITION(A,p,r) ;
           QUICKSORT(A,p,q-1);
           QUICKSORT(A,q+1,r);
       }
   }
   PARTITION(A,p,r){
       x=A[r];i=p-1;
       for(j=p;j≤r-1;j++){
           if  (A[j]≤x){
               i=i+1;
               交换A和A[j]
       }
       }
       交(1)和(2)//注:空(1)和空(2)答案可互换,但两空全部答对方可得分 return  (3)  
   }

(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度,用O记号。最佳情况为(4),平均情况为(5),最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况?(7)。(最佳,平均、最坏)

选项

答案(4)O(nlgn)或O(log2n) (5)O(nlgn)或O(nlog2n) (6)O(n2) (7)最坏

解析
转载请注明原文地址:https://jikaoti.com/ti/Bci7FFFM
0

相关试题推荐
随机试题
最新回复(0)