2. 计算机
  3. 下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。 A：待排序数组 p,r：数组元素下标，从p到r q：划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于i的元素

下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。 A：待排序数组 p,r：数组元素下标，从p到r q：划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于i的元素

admin2010-01-15  54
问题 下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。
   A：待排序数组
   p,r：数组元素下标，从p到r
   q：划分的位置
   x：枢轴元素
   i：整型变量，用于描述数组下标。下标小于或等于i的元素的值，小于或等于枢轴元素的值
   j：循环控制变量，表示数组元素下标
   
(1)假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度(用 O记号)。最佳情况为(4)，平均情况为(5)，最坏情况为(6)。
   (2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7)。 (最佳、平均、最坏)
选项
答案这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时，算法为最佳情况，此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n)，得到时间复杂度为O(nlogn)。当每次为极端不均匀划分时，即长度为n的数组划分后一个子数组为n-1，一个为0，算法为最坏情况，此时时间复杂度可以通过计算递归式T(n)=T(n-1)+O(n)，得到时间复杂度为O(n2)。 对于平均情况的分析较为复杂，假设数组每次划分为9/10：1/10，此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n)，得到时间复杂度为O(nlogn)，因此在平均情况下快速排序仍然有较好的性能，时间复杂度为O(nlogn)。 当所有的n个元素具有相同的值时，可以认为数组已经有序，此时每次都划分为长度为n-1和0的两个子数组，属于最坏情况。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/a0DZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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