如果只想得到一个序列中第k个最小元素之前的部分排序序列,那么

[问答题]

如果只想得到一个序列中第k个最小元素之前的部分排序序列,那么最好应采用何种排序方法? 为什么?如由这样一个序列:57,40,38,11,13,34,48,75,25,6,19,9,7得到其第4个最小元素之前的部分排序序列:

6,7,9,11,.

用你选择的林法实现时,共执行多少次比较?

NEFU_kira

我觉得这道题的题目描述有歧义，11(第4个最小元素)之前的部分排序序列应该理解成原序列中11之前的序列排序也就是11 38 40 57

发表于 2022-10-04 16:37:37 回复(0)

小布丁噢

采用堆排序最合适。依题意可知，只需取得第A个最小元素之前的排序序列，堆排序的时间复杂度为O(n+A×log2n)，若k≤n/ log2n，则时间复杂度为O(n)。对于序列：(57，40，38，11，13，34 48，75， 25，6，19，9，7)，得到第4个最小元素之前的部分序列(6，7，9，11)，使用所选择的算法实现时，其执行比较次数如下：建堆 20次比较得到6 调整 5次比较得到7 调整 4次比较得到9 调整 5次比较得到11 总的比较次数为34次。

发表于 2018-11-07 17:23:40 回复(0)