找出数组中第二大数

有一个int类型的数组，如何找出里面第二大的数，同时算法的时间复杂度是多少？

遍历解法：

思路：第一轮遍历找出第一大MAX，第二轮遍历找出第二大MAX2。

 1 #_*_coding:utf-8_*_
 2 
 3 intArray = [1 , 5 , 6 , 4 , 9 , 8]
 4 
 5 MAX = intArray[0] ;
 6 for i in intArray :
 7     if i > MAX :
 8         MAX = i ;
 9 MAX2 = intArray[0] ;
10 for i in intArray :
11     if (i > MAX2 and i != MAX) :
12         MAX2 = i ;
13 
14 print (MAX2) ;

冒泡解法：

思路：第一轮倒序冒泡将最大数沉到最左，第二轮将次大数沉到次左。

 1 #_*_coding:utf-8_*_
 2 
 3 intArray = [1 , 5 , 6 , 4 , 9 , 8]
 4 
 5 for i in range (len(intArray)-1) :
 6     if (intArray[len(intArray)-i-1] > intArray[len(intArray)-i-2]) :
 7         a = intArray[len(intArray)-i-1] ;
 8         intArray[len(intArray)-i-1] = intArray[len(intArray)-i-2] ;
 9         intArray[len(intArray)-i-2] = a ;
10 
11 for i in range (len(intArray)-1) :
12     if (intArray[len(intArray)-i-1] > intArray[len(intArray)-i-2]) :
13         a = intArray[len(intArray)-i-1] ;
14         intArray[len(intArray)-i-1] = intArray[len(intArray)-i-2] ;
15         intArray[len(intArray)-i-2] = a ;
16 
17 print (intArray[1])