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