使用快速排序算法对含 N(N>=3) 个元素的数组 M 进行排序,若第一趟排序将除枢轴外的N-1个元素划分为 P 和 Q 两个部分,则下列叙述中,正确的是( )。
A. P 和 Q 块间有序
B. P 和 Q 均块内有序
C. P 和 Q 的元素个数大致相等
D. P 和 Q 中均不存在相等的元素
快速排序算法的基本思想是。通过一趟...
用户登录可进行刷题及查看答案
快速排序算法的基本思想是。通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小.然后分别对这两部分继续进行排序,以达到整个序列有序的目标。
在这个问题中,我们在第一趟排序后,将数组M除枢轴外的N-1个元素划分为均不空的P和Q两块。对于这种情况,我们可以得出以下结论: A、P与Q块间有序;这是正确的。在快速排序中,我们选择一个枢轴,然后将所有小于枢轴的元素放在枢轴的左边(即Р块),将所有大于枢轴的元素放在枢轴的右边(即Q块)。因此。Р块中的所有元素都小于Q块中的所有元素,所以P与Q块间是有序的。 B、P与均块内有序:这是错误的。在快速排序的一趟排序过程中,我们只是根据是否小于或大于枢轴来划分元素,而并没有对Р块或Q块内的元素进行排序。因此,虽然Р块和Q块间有序,但Р块和Q块内部可能是无序的。 C、P和Q的元素个数大致相等:这是错误的。在快速排尽中,P块和Q块的元素个数取决于选取的枢轴。如果枢轴恰好是中位数,那么Р块和Q块的元素个数会大致相等。但如果枢轴偏离中位数。那么Р块和Q块的元素个数可能会有很大的不同. D、Р和Q中均不存在相等的元素:这是错误的。在快速排序中,我们只是将元素划分为小于枢轴的部分和大于枢轴的部分。如果原数组中存在相等的元素,都么在划分后的Р块或Q块中仍然可能右在相等的元素。
登录后提交答案
暂无评论,来抢沙发