算法导论9.1-1找第二小的元素 1、证明：在最坏情况下，找到n个元素中第二小的元素需要 $n+ \lceil lgn \rceil -2$次比较。（提示：可以同时找到最小元素） 做以下断言：无论采用何种比较算法，在寻找最小元素的过程中，第二小的元素一定与最小元素做过比较。
因此，要想是我们找到最小元素的比较次数最少，就需要在寻找最小元素的过程中与最小元素发生比较的次数尽量的少。
由于每次我们只能取两个元素进行比较，从而考虑每一轮将我们比较元素两两比较，较小的元素进入下一轮（如比较元素有奇数个，落单的直接进入下一轮），这样比较所得的最小元素比较过的元素是最少的（每轮只有一个）。
我们将比较过程转化为二叉树（以数组 [7,8,1,3,4,5,9]为例）:
1.证明 $n-1$ 其中，除了叶节点外，每个结点都是一次比较的结果。因此该算法中，比较次数为树中度为2的结点数。根据二叉树的性子可以得出比较次数为 $n-1$ （二叉树：度为2的结点数=叶子叶子结点数-1）。可以看出树的每一层只有一个结点与最小元素比较，达到了下界，因此是最优的。
这里的 $n-1$ 次比较下界还有另外的思路。可以把每个元素看成一个集合。集合中用最小元素代表这个集合。初始状态下 $n$个点都是单独的集合，比较后相当于把集合做合并。合并后用最小值代表这个集合。那么初始状态下的 $n$ 个集合，至少经过 $n-1$ 次合并才能得到1个集合。
2.证明 $\lceil lg \rceil -1$ 可以看出，与最小元素比较的次数为树高h-1（根节点的高度为1）。有因为叶节点数个数为n。从而有： $n \leq 2^{h-1}$，故有 $h-1 = \lceil lg n \rceil$,即与最小元素比较的次数至少为 $\lceil lg n \rceil$。
从这 $\lceil lg n \rceil$个元素中找到的最小元素即是第二小的元素。最坏情况下第二小元素第一轮遇到最小元素被淘汰，从而在寻找最小元素的过程中，我们无法得到其他元素与第二小元素比较大小关系。这种情况下，要在 $\lceil lg n \rceil$个元素中找到最小元素需要 $\lceil lg n \rceil - 1$次比较。
综上：最坏情况下，要找到第二小的元素所需的比较次数为 $n + \lceil lg n\rceil -2$ 次比较。
2.算法实现： 根据上面的解释。我们其实只要找到最小元素，然后在最小元素比较过程中比较过的元素记录下来，然后我们在这堆元素（上面证明共$\lceil lg n\rceil$个）中找最小元素即可。
具体实现：对于每一个元素，采用数组或链表的结构，每次比较后胜出的元素记录与它比较的元素在原数组的下标，同时自身进入下一轮的比较，根据上面的图可知，每经过一轮比较，元素被筛选掉一半，直至最终仅剩一个元素时，它就是最小元素，返回与它比较元素的元素集合。最终在该集合中寻找第二小元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 #include <iostream> #include <vector> #include <ctime> #include <cmath> #include <algorithm> using namespace std ;const int INF=0x3f3f3f3f ;class Solution { public : static int cnt; static void init (vector <int > &vec) { srand(time(nullptr )); for_each(vec.begin(),vec.end(),[](int &v){v=rand();}); } static vector <int > findSmallestAndCollection(const vector <int >& vec,vector <int >* paths) { vector <int > winnerIndex(vec.size()); for (int i=0 ;i<winnerIndex.size();++i)winnerIndex[i]=i; while (winnerIndex.size()!=1 ) { winnerIndex=compareAndStore(vec,winnerIndex,paths); } return paths[winnerIndex[0 ]]; } static int findSecondSmallest (const vector <int >& vec,vector <int > *paths) { int smallest2=INF; vector <int > path=Solution::findSmallestAndCollection(vec,paths); for (auto i:path) { if (vec[i]<smallest2){ Solution::cnt++; smallest2=vec[i]; } } return smallest2; } static vector <int > compareAndStore(const vector <int > &arr,const vector <int > &winnerIndex,vector <int >* paths) { vector <int > ret; int sz=winnerIndex.size(); if (sz&1 ) { ret.push_back(winnerIndex[sz-1 ]); --sz; } for (int i=1 ;i<sz;i+=2 ) { if (arr[winnerIndex[i]]<=arr[winnerIndex[i-1 ]]){ ret.push_back(winnerIndex[i]); paths[winnerIndex[i]].push_back(winnerIndex[i-1 ]); } else { ret.push_back(winnerIndex[i-1 ]); paths[winnerIndex[i-1 ]].push_back(winnerIndex[i]); } Solution::cnt++; } return ret; } }; int Solution::cnt=0 ;void showTopTen (vector <int > &vec) sort(vec.begin(),vec.end()); for (int i=0 ;i<vec.size()&&i<10 ;++i) cout << vec[i] << " " ; cout << endl ; } int main () int len; cout << "输入元素个数" <<endl ; cin >> len; vector <int > vec(len);Solution::init(vec); vector <int > *comparePath=new vector <int >[vec.size()]; int smallest2=Solution::findSecondSmallest(vec,comparePath); cout << "Second smallest element :" <<smallest2 << endl ; cout << "Compare time O(n+lgn-2) \n Std:" << (len+ceil (log (len)/log (2 ))-2 ); cout << "\nExtra:" << Solution::cnt << endl ; showTopTen(vec); delete [] comparePath; }
3、总结 该算法主要注重比较次数，但是空间复杂度不乐观（保存比较路径），时间复杂度为 $O(n)$。适合于那种一次比较需要耗费大量时间的值。下面有两篇我解决该题参考的博客。
参考博客 只涉及证明：
博客1：https://blog.csdn.net/qq_33382034/article/details/53495036
包括证明和算法实现（python）
博客2：http://windmissing.github.io/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA/2015-12/9.1-1-second_smallest_element.html
