1.
排序仪召，快速排序寨蹋。
快速排序平均所費時間為nlogn，從小到大排序這n個數(shù)返咱，然后再遍歷序列中后k個元素輸出钥庇，即可牍鞠，總的時間復雜度為O（nlogn+k）=O（n*logn）咖摹。
2.
堆排序 什么是堆?
維護k個元素的最小堆，原理與上述第2個方案一致难述，即用容量為k的最小堆存儲最先遍歷到的k個數(shù)萤晴，并假設它們即是最大的k個數(shù)，建堆費時O（k）胁后，并調整堆（費時O（logk））后店读，有k1>k2>…kmin（kmin設為小頂堆中最小元素）。繼續(xù)遍歷數(shù)列攀芯，每次遍歷一個元素x屯断，與堆頂元素比較，若x>kmin侣诺，則更新堆（用時logk）殖演，否則不更新堆。這樣下來年鸳，總費時O（klogk+（n-k）logk）=O（nlogk）趴久。此方法得益于在堆中，查找等各項操作時間復雜度均為logk（不然搔确，就如上述思路2所述：直接用數(shù)組也可以找出最大的k個元素彼棍，用時O（nk））灭忠。
核心思想：分治法 聊聊分治算法
采用分治算法解決的問題需要滿足的條件(特征):
- . 原問題規(guī)模通常比較大，不易直接解決座硕，但問題縮小到一定程度就能較容易的解決弛作。
- . 問題可以分解為若干規(guī)模較小、求解方式相同(似)的子問題华匾。且子問題之間求解是獨立的互不影響缆蝉。
- . 合并問題分解的子問題可以得到問題的解。
