問題如題目，不過數(shù)組是無序數(shù)組，數(shù)組中元素個數(shù)假設(shè)為n
下面介紹第一種最樸素的做法：
設(shè)定兩個變量，first和second，然后依次遍歷數(shù)組；如果當(dāng)前遍歷元素a[i]比first大，則second = first， first = a[i]；如果當(dāng)前遍歷元素a[i]比first小，則再比較a[i]與second的大小，如果a[i]比second大，則second = a[i]，否則second值不變。那么上面算法的復(fù)雜度是多少呢？我先寫出代碼再分析復(fù)雜度，代碼比較簡單：


其實這個問題很容易就能寫出O(n)復(fù)雜度的算法，反而想寫出比O(n)復(fù)雜度高的還不太容易，所以我們這里就著重分析比較次數(shù)，上面算法可以看出在n>2時，比較次數(shù)跟給定數(shù)組當(dāng)前狀況有關(guān)，比如，如果當(dāng)前數(shù)組已經(jīng)遞增有序，則算法只需要比較n - 1次；但是如果當(dāng)前數(shù)組已經(jīng)遞減有序，則算法需要比較2n - 3次，所以我們可以知道上面算法的最壞情況比較次數(shù)為2n - 3，最好情況比較次數(shù)為n - 1；我們這里假設(shè)數(shù)組中的數(shù)的大小符合均勻隨機分布，則當(dāng)前a[i]比first大的概率為0.5，當(dāng)前a[i]比first小的概率也為0.5，所以總的期望比較次數(shù)=1 + 0.5(n - 2) + 0.5 * 2 * (n - 2) = 1.5n - 2；所以總結(jié)如下：
算法的最壞情況比較次數(shù)為2n - 3，
算法的最好情況比較次數(shù)為n - 1，
算法的期望比較次數(shù)為1.5n - 2；
那么能不能改進(jìn)算法讓使得在最壞情況下也比較1.5n + c次呢？c為一小常數(shù)。答案是肯定的。
上面算法中，在掃描數(shù)組的時候每次取一個元素和first以及second比較，那么我們能不能每次取兩個元素a[i]和a[i + 1]呢？這兩個元素先確定大小關(guān)系，假設(shè)為tmpfirst以及tmpsecond，這只需一次比較，然后再通過類似歸并排序的歸并步驟確定first、second和tmpfirst、tmpsecond兩個有序子數(shù)組合并后的newfirst和newsecond，這只需要確定的2次比較，綜上可知每次取兩個元素的話總的比較次數(shù)為3次，而原來算法確定兩個元素a[i]和a[i + 1]需要2次（最好）或4次（最差）比較。這樣就讓算法固定在1.5n + c次比較，具體c是多少，我們先寫代碼看：


上面算法需要區(qū)分n為偶數(shù)和奇數(shù)的情況，通過分析代碼我們可以得出如下結(jié)論：
若n為偶數(shù)，則總的比較次數(shù) = 1 + 1.5 * (n - 2) = 1.5n - 2；
若n為奇數(shù)，則總的比較次數(shù) = 1 + 1.5 * (n - 3) + 1 = 1.5n - 2.5或總的比較次數(shù) = 1 + 1.5 * (n - 3) + 2 = 1.5n - 1.5
可以知道，上面算法確實可以將總的比較次數(shù)限定在1.5n + c的范圍，且c比較小。
那么現(xiàn)在又有問題了，能不能通過每次取多于2個元素比如每次取3個元素a[i]、a[i  + 1]、a[i + 2]，一次性確定3個元素的大小，比如tmpfirst、tmpsecond、tmpthird，然后再確定first、second以及tmpfirst、tmpsecond、tmpthird這五個元素中前兩大的元素，我們可以計算一下，確定a[i]、a[i + 1]、a[i + 2]三個元素的大小關(guān)系至少需要三次比較，這樣平攤到每個元素需要1次比較，而上面算法確定兩個元素大小只需要一次比較，平攤到一個元素只需要0.5次比較，所以每次取多于2個元素的方法行不通。
那么還有沒有其他的辦法呢？
仔細(xì)分析前面的算法，它的核心思想是每確定a[i]和a[i + 1]的大小關(guān)系之后就緊接著和first以及second比較來更新first和second，那我們能不能先依次確定(a[1]、a[2])，(a[3]、a[4])，...，(a[n - 1]、a[n])，然后再確定(a[1]、a[2]、a[3]、a[4])，...，(a[n - 3]、a[n - 2]、a[n - 1]、a[n])，這樣依次合并，最后確定(a[1]、a[2]、...、a[n])的first和second，這不就是分治的思想嘛…和歸并排序一樣一樣的。代碼如下：


算法是很漂亮，同樣來分析一下比較次數(shù)吧：
根據(jù)遞歸，可以很容易寫出如下遞推式：T(n) = 2T(n/2) + 2，其中2T(n/2)是子問題需要的比較次數(shù)，2是兩個子問題歸并需要的次數(shù)。根據(jù)《算法導(dǎo)論》主定理，我們可以知道T(n)是O(n)的，哈哈！我們至少沒有寫出一個比O(n)高階的算法！但是還沒有辦法確定n前面的系數(shù)到底有多大，我們下面就簡單遞推一下：
T(n) = 2T(n/2) + 2 = 2(2T(n/4) + 2) + 2 = 2[2(2T(n/8) + 2) + 2] + 2 = ... = 2^[log₂^{n - 1]}T(n/ 2^[log₂^{n - 1]} ) + 2¹ + 2² + ... + 2^[log₂^{n - 1]} = (n/2)T(2) + n - 2，又易知T(2)為1，所以T(n) = 1.5n - 2，上面的計算并不是非常嚴(yán)謹(jǐn) ，但是不會影響判斷1.5的得出，所以我們可以看出，雖然采用了分治的方法，但是比較次數(shù)并沒有降低，其實仔細(xì)思考的話會發(fā)現(xiàn)分治和上面的每次取兩個元素比較的思想是等同的。

上面僅僅是針對取數(shù)組中第二大數(shù)來分析的，如果要取數(shù)組中第k大數(shù)的話就不適用了，具體可以參見《算法導(dǎo)論》中位數(shù)與順序統(tǒng)計章節(jié)，里面的介紹很精彩。