方案1:
采用局部淘汰法。選取前100個元素,并排序,記為序列L。然后一次掃描剩余的元素x,與排好序的100個元素中最小的元素比,如果比這個最小的要大,那么把這個最小的元素刪除,并把x利用插入排序的思想,插入到序列L中。依次循環,知道掃描了所有的元素。復雜度為O(100w*100)。
方案2:
采用快速排序的思想,每次分割之后只考慮比軸大的一部分,知道比軸大的一部分在比100多的時候,采用傳統排序算法排序,取前100個。復雜度為O(100w*100)。
方案3:
在前面的題中,我們已經提到了,用一個含100個元素的最小堆完成。復雜度為O(100w*lg100)。