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

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

admin2009-01-10  103
问题 下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。
   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://kaotiyun.com/show/P5DZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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