问答题
如果只想在一个有n个元素的任意序列中得到其中最小的第k(k＜＜n)个元素之前的部分排序序列，那么最好采用什么排序方法?为什么?例如有这样一个序列{57，40，38，11，13，34，48，75，6，19，9，7}，要得到其第4个元素之前的部分有序序列{6，7，9，11}，用所选择的算法实现时，要执行多少次比较?
【正确答案】
【答案解析】一般来讲，当n比较大且要选的数据k远小于n时，采用堆排序方法中的筛选算法siftDown()最好。
例如，对于序列{57，40，38，11，13，34，48，75，6，19，9，7}，选最小数据6，需形成初始堆，进行2×3+2×2+2×2+2×1+1=19次数据比较；选次小数据7时，需用38填补6，再重新形成堆，执行4次数据比较；再选数据9时，需用57填补7，再重新形成堆，执行6次数据比较；选数据11时，需用19填补9，再重新形成堆，执行4次数据比较。注意，按照算法要求，输出11以后，还必须重新形成堆，需要4次数据比较。所以，用堆排序方法对此12个数据取其第4个元素之前的部分有序序列，总的数据比较次数为19+4+6+4+4=37，如下图所示。
例如，对于序列{57，40，38，11，13，34，48，75，6，19，9，7}，选最小数据6，需形成初始堆，进行2×3+2×2+2×2+2×1+1=19次数据比较；选次小数据7时，需用38填补6，再重新形成堆，执行4次数据比较；再选数据9时，需用57填补7，再重新形成堆，执行6次数据比较；选数据11时，需用19填补9，再重新形成堆，执行4次数据比较。注意，按照算法要求，输出11以后，还必须重新形成堆，需要4次数据比较。所以，用堆排序方法对此12个数据取其第4个元素之前的部分有序序列，总的数据比较次数为19+4+6+4+4=37，如下图所示。