2. 计算机
  3. 快速排序的记录移动次数(37)比较次数，其总执行时间为O(nlog2n)。

快速排序的记录移动次数(37)比较次数，其总执行时间为O(nlog2n)。

admin2010-01-17  33
问题 快速排序的记录移动次数(37)比较次数，其总执行时间为O(nlog2n)。
选项 A、大于
B、小于等于
C、小于
D、大于等于
答案B
解析 本题考查快速排序。快速排序采用了一种分治的策略，其具体过程为：第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码；第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。在快速排序中，每次比较后才移动记录，但有时候不需要移动记录，因此，快速排序的记录移动次数不大于比较的次数。但如果记录移动次数等于比较的次数，说明每次比较都要移动记录，是快速排序最坏的情况，在此情况下执行时间为O(n2)。
转载请注明原文地址:https://kaotiyun.com/show/cqjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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