试题详情
简答题如果只想得到一个序列中第k个最小元素之前的部分排序序列，最好采用什么排序方法？为什么？对于序列{57，40，38，11，13，34，48，75，25，6，19，9，7}，得到其第4个最小元素之前的部分序列{6，7，9，11}，使用所选择的排序算法时，要执行多少次比较？
  • 采用堆排序最合适，依题意可知只需取得第k个最小元素之前的排序序列时，堆排序的时间复杂度Ο（n+klog2n），若k≤nlog2n，则得到的时间复杂性是Ο（n）。
    对于上述序列得到其前4个最小元素，使用堆排序实现时，执行的比较次数如下：初始建堆：比较20次，得到6；
    第一次调整：比较5次，得到7；
    第二次调整：比较4次，得到9；
    第三次调整：比较5次，得到11。

  • 关注下方微信公众号，在线模考后查看

热门试题