百度面试题 --- 锦标赛排序

面了一次百度，暂时完成两轮技术面试，感觉每次都好多题目，并且有一些不知道怎么回答，看来准备的还是不够好。

先分享一个题目吧：

给出一个长度是N的数组，现在要找出最大的两个元素，最少要多少次比较。

分析： 如果找出1个最大的，比较次数无疑是 n - 1,

现在如果已经找出最大的了，那么再找第二大的，如果用竞赛排序的方法，可以再使用 logn就可以找到了。 不过不知道怎么证明 这是最小次数。

顺便实现了一下 竞赛排序。

1. public class TournamentSort {   
2.       private class Node//用node来存储竞赛排序过程中的节点，包括里面的数据和数据在数组中的ID  
3.     {          public int data; 
4.         public int id;           
5.         public Node()          { 
6.                       } 
7.         public Node(int _data, int _id)//           { 
8.             data = _data;              id = _id; 
9.         }      } 
10.     public void Adjust(Node[] data, int idx)//当去除最小元素以后，我们要调整数组       { 
11.         while(idx != 0)          { 
12.             if(idx % 2 == 1)//当前id是奇数，说明并列的是idx + 1, 父节点是 (idx-1)/2               { 
13.                 if(data[idx].data < data[idx + 1].data)                  { 
14.                     data[(idx - 1)/2] = data[idx];                  } 
15.                 else                  { 
16.                     data[(idx-1)/2] = data[idx + 1];                  } 
17.                 idx = (idx - 1)/2;              } 
18.             else              { 
19.                 if(data[idx-1].data < data[idx].data)                  { 
20.                     data[idx/2 - 1] = data[idx-1];                  } 
21.                 else                  { 
22.                     data[idx/2 - 1] = data[idx];                  } 
23.                 idx = (idx/2 - 1);              } 
24.         }      } 
25.            
26.     public void Sort(int[] data)      { 
27.         int nNodes = 1;          int nTreeSize; 
28.         while(nNodes < data.length)          { 
29.             nNodes *= 2;          } 
30.         nTreeSize = 2 * nNodes - 1;//竞赛树节点的个数, nNode算出来是为了做成满二叉树            
31.         Node[] nodes = new Node[nTreeSize];//竞赛树用数组存储           //initialize the data  
32.                   int i, j; 
33.         int idx;          for( i = nNodes - 1; i < nTreeSize; i++) //初始化竞赛树数据  
34.         {              idx = i - (nNodes - 1); 
35.             if(idx < data.length)              { 
36.                 nodes[i] = new Node(data[idx], i);              } 
37.             else              { 
38.                 nodes[i] = new Node(Integer.MAX_VALUE, -1);//对于补充的数据，我们初始化成最大。               } 
39.                       } 
40.                   for( i = nNodes - 2; i >= 0; i--)//  
41.         {              nodes[i] = new Node(); 
42.             if(nodes[i * 2 + 1].data < nodes[i * 2 + 2].data)              { 
43.                 nodes[i] = nodes[i*2 + 1];              } 
44.             else              { 
45.                 nodes[i] = nodes[i*2 + 2];              } 
46.         }          //the real sorting procedure  
47.         for( i = 0; i < data.length; i++)//实际排序的过程           { 
48.             data[i] = nodes[0].data;//取出最小的               nodes[nodes[0].id].data = Integer.MAX_VALUE; 
49.             Adjust(nodes, nodes[0].id);               
50.         }           
51.                    
52.     }  }